LeetCode - Sort List

Problem description

description

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Analysis

If we need to sort a list using O(nlogn) algorithms, then we can use merge sort, heap sort.

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null){
            return head;
        }
        
        int len = 0;
        ListNode p = head;
        
        while (p!=null){
            p = p.next;
            len++;
        }
        
        return mergesort(head, len); 
    }
    
    ListNode mergesort(ListNode list, int len){
        if (len <= 1){
            return list;
        }
        
        int mid = len / 2;
        
        ListNode p = list;
        
        while (mid > 1){
            p = p.next;
            mid--;
        }
        
        ListNode right = p.next;
        p.next = null;
        
        ListNode sl = mergesort(list, len/2);
        ListNode sr = mergesort(right, len - len/2);
        
        return merge(sl, sr);
    }
    
    ListNode merge(ListNode list1, ListNode list2){
        ListNode dummy = new ListNode(0);
        
        ListNode p1 = list1;
        ListNode p2 = list2;
        ListNode p = dummy;
        
        while(p1 != null || p2 != null){
            if (p1 == null){
                p.next = p2;
                p2 = p2.next;
            }
            else if (p2 == null){
                p.next = p1;
                p1 = p1.next;
            }
            else{
                if (p1.val <= p2.val){
                    p.next = p1;
                    p1 = p1.next;
                }
                else{
                    p.next = p2;
                    p2 = p2.next;
                }
            }
            
            
            p = p.next;
        }
        
        return dummy.next;
    }
    
}

What to improve

• an improvement is that we don’t need to get the len beforehand, we can use a quick and slower pointer to get the half of the list.