My 8ms C++ O(1) space solution without separating. Any improvement?


  • 0
    A
    ListNode* partition(ListNode* head, int x) {
        ListNode* cur = new ListNode(0);
        cur->next = head;
        head = cur;
        /*find insert position for elements that < x*/
        while (cur->next && cur->next->val < x)
            cur = cur->next;
        ListNode* insPos = cur;
        ListNode* tmp;
        /*keep traversing list, insert lower val elements
        after InsPos and skip >= x elements*/
        while (cur->next) {
            if (cur->next->val < x) {
                tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = insPos->next;
                insPos->next = tmp;
                insPos = insPos->next;
            } else {
                cur = cur->next;
            }
        }
        return head->next;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.