题目：

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.

链接： 

6/4/2017

审题不清，题中只要和target一样大或者比target大的都在比target小的后面，所以不需要按照小，一样大，大这种来区分，只要按照小，不小就可以了。

注意第31行，这是为了避免出现环状输出。large.next应该是null

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     public ListNode partition(ListNode head, int x) {11         if (head == null) {12             return head;13         }14         ListNode dummySmall = new ListNode(-1);15         ListNode dummyLarge = new ListNode(-1);16 17         ListNode cur = head;18         ListNode small = dummySmall;19         ListNode large = dummyLarge;20 21         while (cur != null) {22             if (cur.val < x) {23                 small.next = cur;24                 small = small.next;25             } else {26                 large.next = cur;27                 large = large.next;28             }29             cur = cur.next;30         }31         large.next = null;32         small.next = dummyLarge.next;33         return dummySmall.next;34     }35 }

更多讨论：