LeetCode OJ 86. 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.

刚开始思考这个问题时绕了点弯路，其实很简单，只要把链表中比x小的节点拆下来按顺序链接到一起构成list1，然后把剩下的节点按顺序链接到一起构成list2。最后list1.next=list2即可。代码如下：

 1 public class Solution {
 2     public ListNode partition(ListNode head, int x) {
 3         if(head==null || head.next==null) return head;
 4         
 5         ListNode Partition = head;
 6         
 7         ListNode nhead = new ListNode(0);
 8         nhead.next = null;
 9         ListNode ntail = nhead;
10         
11         ListNode nhead2 = new ListNode(0);
12         nhead2.next = null;
13         ListNode ntail2 = nhead2;
14         
15         ListNode p = null;
16         while(Partition!=null){
17             if(Partition.val < x){
18                 p = Partition.next;
19                 ntail.next = Partition;
20                 ntail = ntail.next;
21                 ntail.next = null;
22                 Partition = p;
23             }
24             else{
25                 p = Partition.next;
26                 ntail2.next = Partition;
27                 ntail2 = ntail2.next;
28                 ntail2.next = null;
29                 Partition = p;
30             }
31         }
32         ntail.next = nhead2.next;
33         return nhead.next;
34     }
35 }