Share my easy understanding 0ms C solution, basic with full comments


  • 0
    R
    struct ListNode* partition(struct ListNode* head, int x) {
            // Initials
    		if (head == NULL) return NULL;
    		if (head->next == NULL) return head;
           
            // An assisting fake node as head
    		struct ListNode* fakeHead;
    		fakeHead->next = head;
    		
    		// good means val smaller than x
    		// Move to next until next is good
    		struct ListNode* nextGood = fakeHead;
    		
    		// Move to next until next is bad
    		struct ListNode* nextBad = fakeHead;
    		
    		// mark the start of the bad sequence
    		struct ListNode* mark = fakeHead;
    		
    		// Mark the end of the good sequence, and obviously it is before mark
    		struct ListNode* beforeMark = fakeHead;
    		
    		// next is good, continue; bad, stop
    		while (nextbad->next->val < x) {
    			nextbad = nextbad->next;
    
    			// All dealt and return
    			if (nextbad->next == NULL) return fakeHead->next;
    		}
    
    		nextgood = nextbad;
    		
    		// The main loop body
    		while (mark->next != NULL) {
    		    
    			// How many bad numbers; next bad, continue; next good, stop
    			while (nextgood->next->val >= x) {
    				nextgood = nextgood->next;
    
    				// All absolutely dealt, return
    				if (nextgood->next == NULL) return fakeHead->next;
    			}
    
    			beforemark = nextgood;
    
    			// Next of beforemark is good, continue; bad, stop
    			while (beforemark->next->val < x) {
    				beforemark = beforemark->next;
    
    				// Start dealing the good part right now
    				if (beforemark->next == NULL) {
    
    					// Dealing good part, move the part to the position
    					beforemark->next = nextbad->next;
    					nextbad->next = nextgood->next;
    					nextgood->next = NULL;
    					return fakeHead->next;
    				}
    			}
    			mark = beforemark->next;
    
    			// Dealing good part, move the part to the position
    			beforemark->next = nextbad->next;
    			nextbad->next = nextgood->next;
    			nextgood->next = mark;
    
    			// Re-placing the 4 pointers at the next loop
    			nextbad = beforemark;
    		}
    		
    		return fakeHead->next;
    }

Log in to reply
 

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