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,
Given1->4->3->2->5->2and x = 3,
return1->2->2->4->3->5.
该题将链表拆成两个，left里存小于x的结点，right里存大于等于x的结点，最后将left和right拼接起来
public class Solution { public ListNode partition(ListNode head, int x) { if (head == null) { return null; } ListNode leftDummy = new ListNode(0); ListNode rightDummy = new ListNode(0); ListNode left = leftDummy, right = rightDummy; //将小于x的结点加入到left里，大于等于x的结点加入到right里 while (head != null) { if (head.val < x) { left.next = head; left = head; } else { right.next = head; right = head; } head = head.next; } //记得给right.next赋值为null right.next = null; left.next = rightDummy.next; return leftDummy.next; } }
原文：http://www.cnblogs.com/bubbleStar/p/6629420.html