Sort a Linked List in O(NLogN)

Loved this question! https://leetcode.com/problems/sort-list/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

It requires a little fundamentals of Sorting: if you use QuickSort, which is the best sorting algorithm on average, you won't be able to guarantee O(NLogN) for all the cases since in the worst case scenario QuickSort performs in O(N^2)-time.
If you want to guarantee O(NLogN), you'll need to select a different method. One that is guaranteed O(NLogN) for all the cases is MergeSort, although it comes with a stack overhead hence not preferred in real applications. But that's what I'm going to use here: MergeSort.

The approach for MergeSort in a nutshell is the following:

• Handle the base cases when the list has zero, one or two elements
• Split the list into 2. You will use the "slow pointer, fast pointer" approach to find the mid-point of the list
• Call recursively for the 2 lists from the previous step
• Now merge the 2 lists in linear time (they are sorted already!)

That's it, worked well, cheers, ACC.

public class Solution
{
 public ListNode SortList(ListNode head)
 {
  if (head == null) return null;
  if (head.next == null) return head;
  if (head.next.next == null)
  {
   if (head.val > head.next.val)
   {
    int temp = head.val;
    head.val = head.next.val;
    head.next.val = temp;
   }
   return head;
  }

  //Find the 1/2
  ListNode back = head;
  ListNode front = head.next;
  while (front != null && front.next != null)
  {
   back = back.next;
   front = front.next;
   front = front.next;
  }

  front = back.next;
  back.next = null;
  back = head;

  return MergeLists(SortList(back), SortList(front));
 }

 private ListNode MergeLists(ListNode l1, ListNode l2)
 {
  ListNode retVal = null;
  ListNode current = null;

  ListNode i1 = l1;
  ListNode i2 = l2;
  while (i1 != null && i2 != null)
  {
   if (i1.val < i2.val)
   {
    if (retVal == null)
    {
     retVal = new ListNode(i1.val);
     current = retVal;
    }
    else
    {
     current.next = new ListNode(i1.val);
     current = current.next;
    }
    i1 = i1.next;
   }
   else if (i1.val > i2.val)
   {
    if (retVal == null)
    {
     retVal = new ListNode(i2.val);
     current = retVal;
    }
    else
    {
     current.next = new ListNode(i2.val);
     current = current.next;
    }
    i2 = i2.next;
   }
   else
   {
    //2x
    for (int i = 0; i < 2; i++)
    {
     if (retVal == null)
     {
      retVal = new ListNode(i1.val);
      current = retVal;
     }
     else
     {
      current.next = new ListNode(i1.val);
      current = current.next;
     }
    }
    i1 = i1.next;
    i2 = i2.next;
   }
  }

  while (i1 != null)
  {
   if (retVal == null)
   {
    retVal = new ListNode(i1.val);
    current = retVal;
   }
   else
   {
    current.next = new ListNode(i1.val);
    current = current.next;
   }
   i1 = i1.next;
  }
  while (i2 != null)
  {
   if (retVal == null)
   {
    retVal = new ListNode(i2.val);
    current = retVal;
   }
   else
   {
    current.next = new ListNode(i2.val);
    current = current.next;
   }
   i2 = i2.next;
  }

  return retVal;
 }
}