Concise and simple C++ solution.


  • 8
    L
    ListNode *partition(ListNode *head, int x) {
            
            ListNode *head1 = new ListNode(0);
            ListNode *head2 = new ListNode(0);
            ListNode *h1 = head1;
            ListNode *h2 = head2;
            while(head)
            {
                int v = head->val;
                if(v < x)
                {
                    head1->next = head;
                    head1 = head1->next;
                } else {
                    head2->next = head;
                    head2 = head2->next;
                }
                head = head->next;
            }
            head2->next = NULL;
            head1->next = h2->next;;
            return h1->next;
        }

  • 3
    F

    same idea, but I guess your dummy node has memory leak issue.

    ListNode *partition(ListNode *head, int x) {
        if (!head || !head->next) {
            return head;
        }
        ListNode dummy1(0);
        ListNode dummy2(0);
        dummy1.next = NULL;
        dummy2.next = NULL;
        ListNode *tail1 = &dummy1;
        ListNode *tail2 = &dummy2;
        
        while (head) {
            ListNode *next = head->next;
            head->next = NULL;
            if (head->val < x) {
                tail1->next = head;
                tail1 = tail1->next;
            } else {
                tail2->next = head;
                tail2 = tail2->next;
            }
            head = next;
        }
        tail1->next = dummy2.next;
        return dummy1.next;
    }
    

Log in to reply
 

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