L86. Partition List

LinkedList

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

Solution:

• create two lists: one is less than x, the other is >= x;

• and then joint two list;

public ListNode partition(ListNode head, int x){
    ListNode less = new ListNode(0), larger = new ListNode(0);
    ListNode curLess = less, curLarger = larger;
    while(head != null){
        if(head.val < x){
            curLess.next = head;
            curLess = curLess.next;
        }else{
            curLarger.next = head;
            curLarger = curLarger.next;
        }
        head = head.next;
    }
    curLarger.next = null;
    curLess.next = larger.next;
    return less.next;
}