96. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Have you met this question in a real interview?  

Example

 

Example 1:
 Input:  list = null, x = 0
 Output: null
 
 Explanation:
 The empty list Satisfy the conditions by itself.

Example 2:
 Input:  list = 1->4->3->2->5->2->null, x = 3
 Output: 1->2->2->4->3->5->null
 
 Explanation:  
 keep the original relative order of the nodes in each of the two partitions.

class Solution { public: /** * @param head: The first node of linked list * @param x: An integer * @return: A ListNode */ ListNode * partition(ListNode * head, int x) { // write your code here if(head == NULL){ return NULL; } ListNode *dummyLeft = new ListNode(0); ListNode *dummyRight = new ListNode(0); ListNode *left = dummyLeft; ListNode *right = dummyRight; while(head != NULL){ if(head->val >= x){ dummyRight->next = head; head = head->next; dummyRight = dummyRight->next; } else{ dummyLeft->next = head; head = head->next; dummyLeft = dummyLeft->next; } } dummyRight->next = NULL; dummyLeft->next = right->next; return left->next; } };