Using MergeSort(Java)


  • 0
    S
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        int length = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            ++length;
        }
    
        ListNode cur = head;
        for (int i = 0; i < length / 2 - 1; ++i) {
            cur = cur.next;
        }
        ListNode right = sortList(cur.next);
        cur.next = null;
        ListNode left = sortList(head);
        
        head = new ListNode(0);
        cur = head;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        
        if (left != null) {
            cur.next = left;
        } else {
            cur.next = right;
        }
    
        return head.next;        
    }
    

    You can still use two pointer instead of using list length, it will reduce the constants. However, it's more easy and readable to use length of the list.


Log in to reply
 

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