Merge two sorted singly Linked Lists without creating new nodes

Technology Community › Category: Linked Lists › Merge two sorted singly Linked Lists without creating new nodes

VietMX Staff asked 3 years ago

Problem

You have two singly linked lists that are already sorted, you have to merge them and return a the head of the new list without creating any new extra nodes. The returned list should be sorted as well.

The method signature is:

Node MergeLists(Node list1, Node list2);

Node class is below:

class Node{
   int data;
   Node next;
}

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Here is the algorithm on how to merge two sorted linked lists A and B:

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

Here C will be the output list.

There are two solutions possible:

Recursive approach is
1. Of the two nodes passed, keep the node with smaller value
2. Point the smaller node’s next to the next smaller value of remaining of the two linked lists
3. Return the current node (which was smaller of the two nodes passed to the method)

Iterative approach is better for all practical purposes as scales as size of lists swells up:
1. Treat one of the sorted linked lists as list, and treat the other sorted list as `bag of nodes’.
2. Then we lookup for correct place for given node (from bag of nodes) in the list.

Complexity Analysis

The run time complexity for the recursive and iterative solution here or the variant is O(n).

Implementation

Recursive solution:

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}

Recursion should not be needed to avoid allocating a new node:

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  Node head;
  if (list1.data < list2.data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  while(list1.next != null) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  } 
  list1.next = list2;
  return head;
}

Question Tags: Linked Lists, Middle Level