C++ AC implementation


  • 0
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            if(!head)  return head;
            ListNode *dummy=new ListNode(-1);    dummy->next=head;
            ListNode *small_head=NULL, *big_head=NULL;
            ListNode *small_cur, *big_cur;
            ListNode* cur=head;
            while(cur){
                if(cur->val < x){
                    if(small_head==NULL)  { small_head=cur;  small_cur=cur; }
                    else { small_cur->next=cur; small_cur=cur; }
                }
                else{
                    if(big_head==NULL)  { big_head=cur;  big_cur=cur; }
                    else { big_cur->next=cur; big_cur=cur; }
                }
                cur=cur->next;
            }
            
            if(small_head==NULL || big_head==NULL){
                return head;
            }
            
            small_cur->next=big_head;
            big_cur->next=NULL;
            return small_head;
        }
    };

  • 1

    By using 2 dummy node independently for the bigger node and smaller node we can get much more concise Implementation.

    class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            ListNode node1(0), node2(0);
            ListNode *p1=&node1, *p2=&node2;
            while(head){
                if(head->val<x){
                    p1->next=head;
                    p1=p1->next;
                }else{
                    p2->next=head;
                    p2=p2->next;
                }
                head=head->next;
            }
            p2->next=NULL;
            p1->next=node2.next;
            return node1.next;
        }
    };

Log in to reply
 

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