My Accepted solution


  • 3
    D

    Solution:

    Keep going along our list. When we at node that greater or equal x, we remove this node from our list and move it to list of nodes greater than x.

    Then we need connect tail our list and list of nodes greater than x.

    class Solution {
    public:
        ListNode *partition(ListNode *head, int x) {
            if (!head) return NULL;
            ListNode * iterator = head; 
            
            ListNode * start = new ListNode(0); // list of nodes greater than x
            ListNode * tail = start;
            
            ListNode * newHead = new ListNode(0); 
            newHead -> next = head;
            ListNode * pre = newHead; // previous node, we need it for removing
            
            
            while (iterator) {
                if (iterator -> val >= x) {
                    pre -> next = iterator -> next; // remove from our list
                    tail -> next = iterator; // add to list of nodes greater than x
                    tail = tail -> next;
                    iterator = iterator -> next;
                    tail -> next = NULL;
                }
                else
                    pre = iterator, iterator = iterator -> next;
            }
            pre -> next = start -> next;
            return newHead -> next;
        }
    };

  • 0
    J
    ListNode *partition(ListNode *head, int x) {
        ListNode* emptyNode = new ListNode (0);
        emptyNode->next = head;
        
        ListNode **p = &head, **lt = &emptyNode, **lg = &emptyNode;
    
    	while (*p) {
    		if ((*p)->val < x) {
    			if(lg == lt) {
    				lt = p;
    				lg = p;
    			}
    			else {
    				ListNode* t = *p;
    				(*lg)->next = (*p)->next;
    				t->next = (*lt)->next;
    				(*lt)->next = t;
    				
    				lt = &(*lt)->next;
    			}
    		}
    		else {
    			lg = p;
    		}
    		p = &(*lg)->next;
    	}
    
    	return  emptyNode->next;
    }
    

    how about this solution? I hope to simplify this function, but I don't known how to do.


Log in to reply
 

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