86. Partition List

Problem:

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.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

5/30/2018 update:
Analysis:
Copy val of node and create new one is cheating. Can not pass interview.

How to partition is intuitive. But remember to cut greater parts last node, assign its next to null to avoid cycle.

Solution:

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode p1 = dummy1, p2 = dummy2;
        while (head != null) {
            if (head.val < x) {
                p1.next = head;
                p1 = head;
            } else {
                p2.next = head;
                p2 = head;
            }
            head = head.next;
        }
        p2.next = null;
        p1.next = dummy2.next;
        return dummy1.next;
    }
}

--------------------------------------------------------------------------------------------------------------------------



思路：
需要把链表分成2份，一份存小的，一份存大的。left dummy 和right dummy。最后把left和right连起来。

dummy的用处就是保持链表头，再处理的时候要复制另外一个node去做操作。比如这道题先申明leftdummy and rightDummy, 实际处理的时候是用的left and rigth，初始化为left dummy, right dummy。 当left 和right往下走的时候dummy不变。