[LeetCode] 86. Partition List

Problem

Given the head of 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.

BCR(Best Conceivable Runtime)

To judge the value of the node is whether grater than x or not, we need to visit all nodes in the linked list at least once. So the best conceivable runtime is $O(N)$.

Solution

This problem seems like reverse version of merge() function in merge sort algorithm. merge() merges two sorted arrays into one arrays. But in this problem, we need to divide one linked list at two different lists,ls and gt, and then merge them to one.

In each iteration, If the value of the node is less than x, add the node to lsTail, or not, to gtTail. Then ls list contains all nodes whose value is less than x in given list, gt list contains the others in stable order.

class Solution {
    public ListNode partition(ListNode node, int x) {
        if (node == null) return node;
        ListNode lsHead = null;
        ListNode lsTail = null;
        ListNode gtHead = null;
        ListNode gtTail = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = null;
            if (node.val < x) {
                if (lsHead == null) {
                    lsHead = node;
                    lsTail = node;
                } else {
                    lsTail.next = node;
                    lsTail = node;
                }
            } else {
                if (gtHead == null) {
                    gtHead = node;
                    gtTail = node;
                } else {
                    gtTail.next = node;
                    gtTail = node;
                }
            }
            node = next;
        }
        if (lsHead == null) {
            return gtHead;
        }
        lsTail.next = gtHead;
        return lsHead;
    }
}

Merging two different lists can be done by just connecting the tail of ls to the head of gt. The time complexity is $O(N)$ because it can go through whole nodes in the list just in one pass.