Merge two sorted linked lists

Given 2 sorted linked lists, merge the lists to a single sorted linked list.
Example:

List1: 2 -> 4 -> 5 -> 6 -> 8 -> 9
List2: 1 -> 3 -> 7
Merged List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9


Video coming soon!



Subscribe for more updates


Algorithm/Insights

Create a mergeNext node which points to smaller head.
Keep traversing the lists, node by node.
If first list element is smaller, point mergedNext node to first list element and move first list forward by one node else point mergedNext to second list element.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given 2 sorted linked lists, merge the lists to a single sorted linked list.
 *
 * @author Saurabh
 */
public class LinkedList {
	Node head;
	
	// Add a new node to the front of the linked list
	public void addToFront(int data) {
		Node n = new Node(data);
		n.next = head;
		head = n;
	}
	
	// Print list elements
	public void printList() {
		Node tmp = head;
		while(tmp != null) {
			System.out.print(tmp.data + " ");
			tmp = tmp.next;
		}
		System.out.println();
	}
	
	// Merge 2 sorted lists to form a single sorted list
	public void mergeList(LinkedList list) {
		
		if(list == null || list.head == null) {
			return;
		}
		if(head == null) {
			head = list.head;
			return;
		}
		
		Node tmp1 = head;
		Node tmp2 = list.head;
		if(tmp1.data < tmp2.data) {
			head = tmp1;
			tmp1 = tmp1.next;
		} else {
			head = tmp2;
			tmp2 = tmp2.next;
		}
		Node mergedNext = head;

		while(tmp1 != null && tmp2 != null) {
			if(tmp1.data < tmp2.data) {
				mergedNext.next = tmp1;
				tmp1 = tmp1.next;
			} else {
				mergedNext.next = tmp2;
				tmp2 = tmp2.next;
			}
			mergedNext = mergedNext.next;
		}
		
		if(tmp1 != null) {
			mergedNext.next = tmp1;
		} else {
			mergedNext.next = tmp2;
		}
	}
	
	public static void main(String[] args) {
		LinkedList list1 = new LinkedList();
		list1.addToFront(9);
		list1.addToFront(8);
		list1.addToFront(6);
		list1.addToFront(5);
		list1.addToFront(4);
		list1.addToFront(2);

		LinkedList list2 = new LinkedList();
		list2.addToFront(7);
		list2.addToFront(3);
		list2.addToFront(1);

		list1.mergeList(list2);
		System.out.println("Merged List:");
		list1.printList();
	}
}

class Node {
	int data;
	Node next;	

	public Node(int data) {
		this.data = data;
	}
}
		

Order of the Algorithm

Time Complexity is O(n+m)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.


    Saurabh Kumar