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.
https://oj.leetcode.com/problems/partition-list/
思路：新建两个链表头，然后遍历原链表根据大小分别添加到新链表头后边，最后合并两个新链表。
public class Solution { public ListNode partition(ListNode head, int x) { if (head == null) return head; ListNode head1 = new ListNode(-1); ListNode head2 = new ListNode(-1); ListNode p = head; ListNode p1 = head1; ListNode p2 = head2; while (p != null) { if (p.val < x) { p1.next = p; p1 = p1.next; } else { p2.next = p; p2 = p2.next; } p = p.next; } p1.next = head2.next; p2.next = null; return head1.next; } public static void main(String[] args) { ListNode head = ListUtils.makeList(new int[] { 1, 4, 3, 2, 5, 2 }); ListUtils.printList(head); new Solution().partition(head, 3); ListUtils.printList(head); } }
[leetcode] Partition List,布布扣,bubuko.com
原文：http://www.cnblogs.com/jdflyfly/p/3819162.html
