148. Sort List Leetcode Solution

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head ->next == NULL)
            return head;
        
        //middle of linked list
        ListNode *temp = NULL;
        ListNode *slow = head;
        ListNode *fast = head;
        
        while(fast !=  NULL && fast -> next != NULL){
            temp = slow;
            slow = slow->next;          
            fast = fast ->next ->next;  
            
        }   
        temp -> next = NULL;            
        
        ListNode* l1 = sortList(head);  //2   
        ListNode* l2 = sortList(slow);  //1 
        
        return mergeTwoLists(l1, l2);         
            
    }
    

    ListNode* mergeTwoLists(ListNode* left, ListNode* right) {
        
        if(left == NULL)  return right;
        if(right == NULL) return left;

        ListNode *ans = new ListNode(-1); 
        ListNode *mptr = ans;
        
    while(left!=NULL && right!=NULL){
            if(left->val<=right->val){
                mptr->next = left;
                mptr = left;
                left = left->next;
            }
            else{
                mptr->next = right;
                mptr = right;
                right = right->next;
            }
        }
    
    if(left!=NULL){
        mptr->next=left;
    }
    if(right!=NULL){
        mptr->next=right;
    }
    
    return ans->next;
    }
};

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;
  }

}

def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  dummy = ListNode(0)
  dummy.next = head

  # Grab sublists of size 1, then 2, then 4, etc, until fully merged
  steps = 1
  while True:
    # Record the progress of the current pass into a single semi sorted list by updating
    # the next of the previous node (or the dummy on the first loop)
    prev = dummy

    # Keep track of how much is left to process on this pass of the list
    remaining = prev.next

    # While the current pass though the list has not been completed
    num_loops = 0
    while remaining:
      num_loops += 1

      # Split 2 sublists of steps length from the front
      sublists = [None, None]
      sublists_tail = [None, None]
      for i in range(2):
        sublists[i] = remaining
        substeps = steps
        while substeps and remaining:
          substeps -= 1
          sublists_tail[i] = remaining
          remaining = remaining.next
        # Ensure the subslist (if one was made) is terminated
        if sublists_tail[i]:
          sublists_tail[i].next = None

      # We have two sublists of (upto) length step that are sorted, merge them onto 
      # the end into a single list of (upto) step * 2
      while sublists[0] and sublists[1]:
        if sublists[0].val <= sublists[1].val:
          prev.next = sublists[0]
          sublists[0] = sublists[0].next
        else:
          prev.next = sublists[1]
          sublists[1] = sublists[1].next
        prev = prev.next
      
      # One list has been finished, attach what ever is left of the other to the end
      if sublists[0]:
        prev.next = sublists[0]
        prev = sublists_tail[0]
      else:
        prev.next = sublists[1]
        prev = sublists_tail[1]
    
    # Double the steps each go around
    steps *= 2

    # If the entire list was fully processed in a single loop, it means we've completely sorted the list and are done
    if 1 >= num_loops:
      return dummy.next