Problem

Given two sorted Linked Lists, how to merge them into the third list in sorted order?

Example

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Merged List: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Solution

Here is the pseudocode:

  • Create a new node say result
  • Navigate through both the linked lists at the same time, starting from head
  • Compare the first node values of both the linked lists
  • Whichever is smaller, add it to the result node
  • Move the head pointer of the linked list whose value was smaller
  • Again compare the node values
  • Keep doing until one list gets over
  • Copy the rest of the nodes of unfinished list to the result

The key to solve the problem is defining a fake head or dummy head to reduce edge case.

Method 1 - Iterative and Creating New List

Then compare the first elements from each list. Add the smaller one to the merged list. Finally, when one of them is empty, simply append it to the merged list, since it is already sorted.

Note that, we’re creating new nodes for the resulting Linked List instead of using the nodes of the supplied LinkedLists directly. This solution will use extra space, but is recommended in the real world because we’re not modifying the LinkedLists supplied in the arguments.

Code

Java
  private static ListNode mergeSortedLinkedLists(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode p = head;
    
    while(l1 != null || l2 != null) {
      int minVal;
      if (l1 == null) {
        minVal = l2.val;
        l2 = l2.next;
      } else if (l2 == null) {
        minVal = l1.val;
        l1 = l1.next;
      } else if(l1.val <= l2.val) {
        minVal = l1.val;
        l1 = l1.next;
      } else {
        minVal = l2.val;
        l2 = l2.next;
      }
		p.next = new ListNode(minVal);
		p = p.next;
    }

    return head.next;
  }

Method 2 - Iterative with In-place Modification

Video Walkthrough:

If you don’t want to create new nodes, then you can use the supplied LinkedList nodes directly:

Code

Java

Solution 1:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode p = head;

    while (l1 != null || l2 != null) {
        if (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;
        } else if (l1 == null) {
            p.next = l2;
            break;
        } else if (l2 == null) {
            p.next = l1;
            break;
        }
    }

    return head.next;
}

Using && to instead of || above:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode p = head;

    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;
	}else if(l2 != null) {
		p.next = l2;
	}

    return head.next;
}

Method 3 - With Recursion

Base Case : If List A gets finished , return List B. If List B gets finished, return List A.

  • Create a result node and initialize it as NULL
  • Check which node (List A or List B) has a smaller value.
  • Whichever is smaller, add it to the result node.
  • Make recursive call and add the return node as result.next result.next = recurrsionMerge(nA.next, nB)

Code

Java
private static ListNode mergeSortedLinkedLists(ListNode l1, ListNode l2) {
    if(l1 == null) {
      return l2;
    } else if (l2 == null) {
      return l1;
    }

    ListNode result = null;
    if(l1.val <= l2.val) {
      result = new ListNode(l1.val);
      result.next = mergeSortedLinkedLists(l1.next, l2);
    } else {
      result = new ListNode(l2.val);
      result.next = mergeSortedLinkedLists(l1, l2.next);
    }
    return result;
  }