Merge Sort Linked List

4 -> 2 -> 6 -> -3 -> 5 -> null, is sorted to -3 -> 2 -> 4 -> 5 -> 6

Solution: MergeSort recursive

Recursion Tree:

                                4231
                     42                       31
                4            2             3       1
--------------------------------------------------------------------
                     24                       13
                                1234 

Step 1: split left and right until one element

public ListNode split(ListNode head){
    if (head == null) return head;
    ListNode slow = head;
    ListNode fast = head;
    while(fast.next != null && fast.next.next != null){
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }

Gets middle point

Time Comp: O(fast + slow pointer) = O(1.5N)

Space Comp: O(1)

Step 2: Combine two linkedlists with dummyhead

public ListNode combine(ListNode one, ListNode two){
    ListNode newHead = new ListNode(0); //return pointer

    ListNode head = newHead; //travelling pointer

    while (one != null && two != null){
      if (one.value < two.value){
        head.next = one;
        head = one;
        one = one.next;
      } else {
        head.next = two;
        head = two;
        two = two.next;
      }
    }

    if (one != null){
      while(one != null){
        head.next = one;
        head = one;
        one = one.next;
      }
    }

    if (two != null){
      while (two != null){
        head.next = two;
        head = two;
        two = two.next;
      }
    }

    return newHead.next;
  }

Time Comp: O(N)

Space Comp: O(1)

Main Function:

public ListNode mergeSort(ListNode head) {
    if ( head == null || head.next == null) return head; //if len 1 or null
    ListNode middle = split(head);
    ListNode middleNext = middle.next;
    middle.next = null;

    ListNode left = mergeSort(head);
    ListNode right = mergeSort(middleNext);

    ListNode res = combine(left, right);

    return res;

  }