O(N) mergesort solution


  • 0
    V
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        int print = 0;
        public ListNode sortList(ListNode head) {
            ListNode p = head;
            int len = 0;
            while (p != null) {
                len++;
                p = p.next;
            }
            return sortListHelper(head, len);
        }
        
        private ListNode sortListHelper(ListNode head, int len) {
            if (head == null || head.next == null) {
                return head;
            }
            
            ListNode mid = getMid(head, len);
            ListNode leftList = sortListHelper(head, len / 2);
            ListNode rightList = sortListHelper(mid, len / 2);
            
            // merge here
            ListNode result = new ListNode(-1);
            ListNode p = result;
            ListNode p1 = leftList;
            ListNode p2 = rightList;
            while (p1 != null || p2 != null) {
                ListNode next = null;
                if (p1 == null) {
                    next = p2;
                    p2 = p2.next;
                } else if (p2 == null) {
                    next = p1;
                    p1 = p1.next;
                } else {
                   if (p1.val < p2.val) {
                       next = p1;
                       p1 = p1.next;
                   } else {
                       next = p2;
                       p2 = p2.next;
                   }
                }
                
                p.next = next;
                p = p.next;
            }
            
            return result.next;
        }
        
        private ListNode getMid(ListNode head, int len) {
            ListNode p = head;
            int count = 1;
            while (count < (len / 2)) {
                p = p.next;
                count++;
            }
            
            ListNode p1 = p.next;
            p.next = null;
            return p1;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.