Merging Two Sorted LinkedLists

Suppose we are given two LinkedLists which are sorted in increasing order and we need to merge them into one. We will create a method, mergeLinkedList(), which will traverse both the LinkedLists, merge them into a single LinkedList, and return the single LinkedList.
The new returned LinkedList will have all the nodes which are present in both original LinkedLists.
If we have,

LikedList1: 2 -> 5 -> 9 -> 12 -> 15 -> 20

And

LinkedList2: 3 -> 7 -> 10 -> 17 -> 22

then our method should return the head pointer pointing to a merged LinkedList.

Merged LinkedList: 2 -> 3 -> 5 -> 7 -> 9 -> 10 -> 12 -> 15 -> 17 -> 20
->22

Methods of Merging

Method: Using Dummy Nodes

In this example we will create a dummy node as a result of our merged LinkedList. The tail pointer will point to the dummy node initially and then we will have a tail pointer pointing to the last node of our result list.

Algorithm for Dummy Nodes

Declaration
create two Nodes
dummyNode =null
tail = dummyNode;

Execution
Step 1:
if List1=null
we have traversed the List1 or List1 is empty
then tail.next will point to List2

if List2=null
we have traversed the List2 or List2 is empty
then tail.next will point to List1

Step 2:
check if list1.data < list2.data
then tail.next will point to node containing List1.data
update list1=list.next
else
tail.next will point to node containing List2.data
update list2=list.next

Step 3:
if both lists not processed then
update tail and go to step 1
else go to Step 4

Step 4: Return dummyNode.next

Java Implementation for Dummy Nodes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
  //will return a node pointing to Result List
  Node mergeLinkedList(Node listA, Node listB) {

    //create dummy Node
    Node dummyNode = new Node();

    Node tail = dummyNode;

    //will break out of Loop
    while (true) {
      //check if listA is empty of traversed
      if (listA == null) {
        tail.next = listB;
        break;
      }
      //check if listB is empty of traversed
      if (listB == null) {
        tail.next = listA;
        break;
      }

      /* 
		check which listdata is lesser will be appended to
		 tail.next
        */
      if (listA.data <= listB.data) {
        tail.next = listA;
        listA = listA.next;
      } else {
        tail.next = listB;
        listB = listB.next;
      }

      //update tail
      tail = tail.next;
    }
    //returning the Result List
    return dummyNode.next;
  } //method Ends

} //Class Ends

Method: Using Recursion

In the above method we tried the iterative approach using dummy nodes. Now we will try the recursion technique to merge two sorted LinkedLists. There is less code than with the iterative approach as it uses the call stack to call itself to work with passed arguments.

Algorithm

Step 1: Call made to mergeLinkedList() and list1 and List2 will be passed

Step 2:
if list1 is empty return list2
if list2 is empty return list1

Step 3:
if list1.data < list2.data
then call mergeLinkedList(list1.next, list2) to Step 1
and return list1
else
call mergeLinkedList(list1, list2.next) to Step 1
and return list2

Java Implementation Using Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
  //Result List will listBe returned
  Node sortedMerge(Node listA, Node listB) {
    if (listA == null) return listB;
    if (listB == null) return listA;

    if (listA.dlistAtlistA < listB.dlistAtlistA) { //call mergeLinkedList recurively
      listA.next = SortedMerge(listA.next, listB);
      return listA;
    } else { //call mergeLinkedList recurively
      listB.next = SortedMerge(listA, listB.next);
      return listB;
    }

  }
}

Method: Reversing LinkedLists

In this method we will maintain both the LinkedLists in decreasing order; this means both LinkedLists will be reversed. Then, comparing the head of each list and adding to the last of the resultant list will get the LinkedList in increasing order.

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {

  Node reverseLL(Node A) {
    Node prev = null;
    Node current = A;
    Node next = null;
    while (current != null) {
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    A = prev;
    return A; //returning reversed LList

  }
  //Result List will listBe returned
  Node sortedMerge(Node listA, Node listB) {
    listA = reverseLL(listA);
    listB = reverseLL(listB);

    Node res = null;
    Node temp = null;

    while (listA != null && listB != null) {

      if (listA.data >= listB.data) {
        temp = listA.next;

        listA.next = res;
        res = listA;

        listA = temp;
      } else {

        temp = listB.next;
        listB.next; = ress;
        res = listB;
        listB = temp;
      }

    }

  } //methodSM Ends
}

Method: Using Local Reference

In this method we will use a local reference variable which will point to the head of the result node. We will use infinite iteration to execute the same.

Algorithm

Step 1: Call made to mergeLinkedList() and list1 and List2 will be passed

Step 2:
if list1 is empty return list2
if list2 is empty return list1

Step 3:
Loop ,Iteration for each Node
if list1.data < list2.data
then call put current head of list1 in next of result
if list2.data < list1.data
then call put current head of list2 in next of result

check if any list is empty
then add second list to end of result ilst and break

return the result

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  //Result List will listBe returned
  Node sortedMerge(Node listA, Node listB) {
    Node resultLL = null;
    if (listA == null) return listB;
    if (listB == null) return listA;

    for (int i = 1; i > 0;) {
      if (listA.data < listB.data) {
        resultLL.next = listA;
        listA = listA.next;
      } else {
        resultLL.next = listB;
        listB = listB.next;
      }
      if (listA == null) {
        resultLL.next = listB;
        break;
      }
      if (listB == null) {
        resultLL.next = listA;
        break;
      }
    } //for loop ends      
  }
}