[leetcode] 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.

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);
    }

}