Java merge sort solution


  • 163
    public class Solution {
      
      public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
          return head;
            
        // step 1. cut the list to two halves
        ListNode prev = null, slow = head, fast = head;
        
        while (fast != null && fast.next != null) {
          prev = slow;
          slow = slow.next;
          fast = fast.next.next;
        }
        
        prev.next = null;
        
        // step 2. sort each half
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        
        // step 3. merge l1 and l2
        return merge(l1, l2);
      }
      
      ListNode merge(ListNode l1, ListNode l2) {
        ListNode l = new ListNode(0), p = l;
        
        while (l1 != null && l2 != null) {
          if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
          } else {
            p.next = l2;
            l2 = l2.next;
          }
          p = p.next;
        }
        
        if (l1 != null)
          p.next = l1;
        
        if (l2 != null)
          p.next = l2;
        
        return l.next;
      }
    
    }

  • 20
    B

    I don't understand why it is constant space complexity? You call merge function log(length) times right? Each time you make a new ListNode l which next property is the returned list. By the way can I do it on l1 without a new listnode?


  • 4

    The split part is clear and easy to understand, but the merge part uses O(n) space,


  • -6
    K

    The merge creates 1 ListNode that is all, the space complexity is not O(n), but O(1)


  • 14
    O

    Since this is a recursion method, the space complexity is O(log(n)) not O(1). I doubt this method pass OJ.


  • -3
    8

    I think leetcode's OJ system doesn't check space usage, unless you make a stackoverflow exception


  • -7
    X

    I agree with you, the space complexity is O(1). Because all the original nodes was already created in the memory (Heap), only one new ListNode created.


  • 0
    H
    This post is deleted!

  • -1
    X

    @otnt I agree with you,the number of new nodes is related to nums of merge-invoking


  • -2
    S

    The space complexity in merge function here is O(1), for the new node created. And it is not O(n) because, we are just re-assigning the pointers to already present nodes. Beautiful Solution.


  • 3
    W

    @SanD @xshen93
    You forgot the space usage by stack in recursion.

    // step 2. sort each half
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);


  • 6
    S

    @wei88
    You are indeed right, the space complexity is O(logn), because the sortList function is called recursively. Also, a new node is created for each time a merge function is called. Since both merge and sortList are called logn times, the space is O(logn).


  • 1

    I dont quite understand why we need to define a "pre" node pointing to the node before slow. You use the PRE node to cut the linked list but what if I want to use the SLOW node? Suppose we have a linked list "5->4->1->3->2", when we finish the pre-slow-fast movement once, the result linked list should be "5->4" and "1->3->2" while we have "5->4->1" and "3->2" for using slow-fast movement. What's the difference between these two?


  • 0
    B
    This post is deleted!

  • 1
    B

    @传说选手 You need to consider list with two nodes. eg 1->2. If you are not using pre, you can't get two list 1 -> null, 2 -> null.


  • 0
    C

    have some trouble understanding why it has to be

    '''
    prev.next = null;

    '''
    I understand it is used to disconnect the linkedlist, but why can't I use slow.next=null here?(The compiler says stackoverflow exception)


  • 9

    @cqy0118 prev points to the ListNode before slow. If we do slow.next = null then when there are only two elements left, it will be a infinite loop, since slow will always point to the second node and sort(head) will fail to divide the last two nodes and always result in the last two nodes, hence the stack overflow error.


  • 0
    B

    Nice explanation with comments inside code!


  • -1
    Z
    This post is deleted!

  • 0
    M

    @ZhassanB It still uses extra space for the recursive calls though.


Log in to reply
 

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