LeetCode 148. Sort List

Problem:

Sort a linked list in O(n log n) time using constant space complexity.

Solution:

Three way quick sort

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        head = quicksort(head);
        return head;
    }
    
    private ListNode quicksort(ListNode pivot) {
        if (pivot == null || pivot.next == null)
            return pivot;
        ListNode prev1 = new ListNode(0), prev2 = new ListNode(0), prev = new ListNode(0);
        ListNode dummy1 = prev1, dummy2 = prev2, dummy = prev;
        ListNode current = pivot;
        while (current != null) {
            if (current.val < pivot.val) {
                prev1.next = current;
                prev1 = prev1.next;
            }
            else if (current.val > pivot.val) {
                prev2.next = current;
                prev2 = prev2.next;
            }
            else {
                prev.next = current;
                prev = prev.next;
            }
            current = current.next;
        }
        prev1.next = prev2.next = prev.next = null;
        dummy1.next = quicksort(dummy1.next);
        dummy2.next = quicksort(dummy2.next);
        current = dummy1;
        while (current.next != null) current = current.next;
        current.next = dummy.next;
        prev.next = dummy2.next;
        return dummy1.next;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *