Merge Sort A Linked List

1. You are given a partially written LinkedList class.
2. You are required to complete the body of mergeSort function. The function is static and is passed the head and tail of an unsorted list. The function is expected to return a new sorted list. The original list must not change.
3. Input and Output is managed for you. 

Note - Watch the question video for theory of merge sort.

Input Format

Input is managed for you

Output Format

Output is managed for you

Question Video Constraints

1. O(nlogn) time complexity required.

Sample Input

6
10 2 19 22 3 7

Sample Output

2 3 7 10 19 22 
10 2 19 22 3 7 

• Editorial

  The problem deals with sorting a linked list with the help of merge sort. To understand this problem better there are two prerequisite problems that one must have solved earlier as those are sub-parts of the merge sort solution. The problems are:

  1. Get Middle Node of a Linked List: This problem deals with finding the middle node of the linked list, for this, we have used Hare and tortoise approach (or the two pointer approach).

  Below is the implementation in Java:

  public static Node midNode(Node head, Node tail){
                                  Node f = head;
                                  Node s = head;
                                  while (f ! = tail && f.next != tail){
                                  f = f.next.next;
                                  s = s.next;
                                  }
                                  return s;
                                  }

  java false

  2. Merge Sorted Lists: In this problem,we are given two sorted lists and we need to return a sorted resultant of these two lists, here too we have used a two-pointer approach.

  Below is the implementation in Java:

  public static LinkedList mergeTwoSortedLists(LinkedList l1, LinkedList l2) {
                                      LinkedList ml = new LinkedList(); 
                                      Node one = l1.head;
                                      Node two = l2.head;
                                      while (one != null && two != null) {
                                      if (one.data < two.data) {
                                          ml.addLast(one.data);
                                          one = one.next;
                                      } else {
                                          ml.addLast(two.data);
                                          two = two.next;
                                      }
                                      } 
                                      while (one != null) {
                                      ml.addLast(one.data);
                                      one = one.next;
                                      } 
                                      while (two != null) {
                                      ml.addLast(two.data);
                                      two = two.next;
                                      } 
                                      return ml;
                                  }

  java false

  Now with the help of these two functions, we will implement merge sort on a linked list.

  The concept behind the merge sort is the divide and conquer technique, wherein we try to break our problem into smaller parts and then try to solve them and later combine them to get our result. So the main step in the whole recursive solution is to divide the list into two halves. For this, we need to find the middlemost element of the list. After getting the middle node the list can be divided into two halves, the first half can be from head to mid and the second half can be from mid + 1 to tail. Now, these two lists represent the smaller problem of our original problem and are then recurse to our mergeSort() function. We have our faith that recursion can handle the smaller cases and we have our expectation that with the help of these smaller solutions and our work for the rest of the case will lead us to the solution of the larger problem. So to meet the expectation with the help of faith, we assume that the lists retrieve from the two halves of the lists are sorted. Now the only step that remains is to merge the lists which we can easily achieve by calling the mergeTwoSortedLists() function. The return value from this function will be our result.

  Base Case: The base case for this problem will be a single node, as a single node is always sorted. As we know that for a single node both head and tail point to the same node so this condition will occur only when head == tail.

  Below is the implementation in Java:

  public static LinkedList mergeSort(Node head, Node tail){
                                      if(head == tail){
                                      LinkedList br = new LinkedList();
                                      br.addLast(head.data);
                                      return br;
                                      } 
                                      Node mid = midNode(head, tail);
                                      LinkedList fsh = mergeSort(head, mid);
                                      LinkedList ssh = mergeSort(mid.next, tail);
                                      LinkedList sl = mergeTwoSortedLists(fsh, ssh);
                                      return sl;
                                  }

  java false

  Diagrammatic Flow (Recursion Tree)

  

  Time Complexity: O(n)

  The time complexity for the function is linear as the traversal of both the lists are involved. Here we visit each and every element in both the lists which makes our algorithm linear. Here n denotes the combined length of both the lists.

  Space Complexity: O(n)

  The space complexity for the function is linear as we have created an output list with size proportional to the combined length of both lists.

• Asked in Companies
• Related Topics