0148. Sort List

Medium | Linked List + MergeSort | 172 ms (98.38%), 45.6 MB (95.85%)

❓ Problem Statement

Source: LeetCode - Sort List GitHub: Solution / Performance

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the list is in the range [0, 5 * 10^4].

• -10^5 <= Node.val <= 10^5

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Input: head = []
Output: []

💡 Ideas

To meet O(1) memory complexity, we need to do Merge Sort by splitting the linked list into multiple segments bottom-up.

Before splitting, we need to get the length of the input linked list.

Then split the linked list bottom-up by starting with size = 1, this size will grow two times of itself in each iteration by size *= 2 until size >= length.

For the process of splitting and merging, we need to maintain two pointers:

1. splitHead is to check whether the splitting process needs to end or not.

2. mergeHead is for merging two split linked lists so that we can maintain relative order for the next splitting process.

🤖 Python3

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        #  (base case)
        if not head or not head.next: return head
        
        # ==================================================
        #  Linked List + Merge Sort           (Iterative)  =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(1)
        
        length = self.getSize(head)
        ret, size = ListNode(0, head), 1
        
        while size < length:
            splitHead, mergeHead = ret.next, ret
            
            while splitHead:
                left  = splitHead
                right = self.split(size, left)
                
                splitHead = self.split(size, right)
                mergeHead = self.merge(left, right, mergeHead)
            
            size *= 2
        
        return ret.next
        
    def getSize(self, node: ListNode) -> int:
        size, tmp = 0, node
        while tmp: size, tmp = size + 1, tmp.next
        return size
    
    def split(self, size: int, node: ListNode) -> ListNode:
        pre = None
        for i in range(size):
            if not node: break
            pre, node = node, node.next
        
        #  (break the link)
        if pre: pre.next = None
        return node
    
    def merge(self, left: ListNode, right: ListNode, head: ListNode) -> ListNode:
        while left and right:
            if left.val <= right.val: head.next, left = left, left.next
            else: head.next, right = right, right.next
                
            head = head.next
        
        head.next = left if left else right
        while head.next: head = head.next
        return head

🤖 Java

class Solution {
    /**
     * @time  : O(nlog(n))
     * @space : O(1)
     */
    
    public ListNode sortList(ListNode head) {
        /* base case */
        if(head == null || head.next == null) return head;
        
        int len = getLen(head);
        
        int size = 1;
        ListNode ret = new ListNode(0, head);
        
        while(size < len) {
            ListNode splitHead = ret.next, mergeHead = ret;
            while(splitHead != null) {
                ListNode left  = splitHead;
                ListNode right = split(size, left);
                
                splitHead = split(size, right);
                mergeHead = merge(left, right, mergeHead);
            }
            
            size *= 2;
        }
        
        return ret.next;
    }
    
    public int getLen(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while(cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }
    
    public ListNode split(int size, ListNode node) {
        ListNode pre = null;
        for(int i=0 ; i<size ; i++) {
            if(node == null) break; 
            pre = node;
            node = node.next;
        }
        /* break the link */
        if(pre != null) pre.next = null;
        return node;
    }
    
    public ListNode merge(ListNode left, ListNode right, ListNode head) {
        while(left != null && right != null) {
            if(left.val <= right.val) {
                head.next = left;
                left = left.next;
            } else {
                head.next = right;
                right = right.next;
            }
            head = head.next;
        }
        head.next = (left != null) ? left : right;
        while(head.next != null) head = head.next;
        return head;
    }
}