86. Partition List.md

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.

For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.

tag:

• two pointers

Solution

java

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

go