[Leetcode] 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.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
No words!
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *partition(ListNode *head, int x) { 12 if (head == NULL) return head; 13 ListNode *h = new ListNode(-1); 14 h->next = head; 15 ListNode *pre = h, *cur = h, *tmp; 16 while (cur != NULL && cur->next != NULL) { 17 if (cur->next->val < x && cur != pre) { 18 tmp = cur->next; 19 cur->next = tmp->next; 20 tmp->next = pre->next; 21 pre->next = tmp; 22 pre = pre->next; 23 } else if (cur->next->val < x && cur == pre) { 24 pre = pre->next; 25 cur = cur->next; 26 } else { 27 cur = cur->next; 28 } 29 } 30 return h->next; 31 } 32 };