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.

 

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     public int val; 5  *     public ListNode next; 6  *     public ListNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     // this solution doesn't pass OJ but I think it actually solves the problem.11     public ListNode PartitionInPlace(ListNode head, int x) {12         if (head == null) return null;13         14         ListNode p1 = head, p2 = head;15         16         while (p2 != null)17         {18             if (p2.val < x)19             {20                 if (p1 != p2)21                 {22                     var tmp = p1.val;23                     p1.val = p2.val;24                     p2.val = tmp;25                 }26                 27                 p1 = p1.next;28             }29             30             p2 = p2.next;31         }32         33         return head;        34     }35     36     public ListNode Partition(ListNode head, int x) {37         if (head == null) return null;38         39         ListNode p1 = new ListNode(1), p2 = new ListNode(2), cur1 = p1, cur2 = p2, cur = head;40         41         while (cur != null)42         {43             var tmp = cur.next;44             cur.next = null;45             if (cur.val < x)46             {47                 cur1.next = cur;48                 cur1 = cur1.next;49             }50             else51             {52                 cur2.next = cur;53                 cur2 = cur2.next;54             }55             cur = tmp;56         }57         58         cur1.next = p2.next;59         return p1.next;        60     }61 }