Code Destine

Problem Statement

You have given two sorted linked lists. Write a program to merge the given list. The return linked list should be made by splicing together the nodes of the given two lists.

Example 

Input :- first = [1, 3, 7, 9, 11], second = [2, 4, 5, 8, 10]
Output :- [1, 2, 3, 4, 5, 7, 8, 9, 10, 11]

Solution

We can use temporary node to solve this problem, here are the steps :-

1. Create two variables temp and head with temporary node assign to it.
2. Initially, two variables L1 and L2 point to the head of the first and second linked list respectively.
3. Compare the value of the L1 node and L2 node.
4. If L1 is smaller than L2, then assign L1 to the next pointer of temp node (temp.next = L1) and move L1 and temp to its next position (temp = temp.next and L1 = L1.next).
5. If L2 is smaller than L1, then assign L2 to the next pointer of temp node (temp.next = L2) and move L2 and temp to its next position (temp = temp.next and L2 = L2.next).
6. If both L1 and L2 are same, then firstly assign L1 to the next pointer of temp node (temp.next = L1) and move L1 and temp to its next position (temp = temp.next and L1 = L1.next) and then in the last assign L2 to the next pointer of temp node (temp.next = L2) and move L2 and temp to its next position (temp = temp.next and L2 = L2.next).
7. Return the next of the head variable as a result.

Program

public class Main {

	public static void main(String[] args) {

		ListNode l1 = null;
		ListNode node = new ListNode(1);
		l1 = node;
		node.next = new ListNode(3);
		node = node.next;
		node.next = new ListNode(7);
		node = node.next;
		node.next = new ListNode(9);
		node = node.next;
		node.next = new ListNode(11);

		ListNode l2 = null;
		node = new ListNode(2);
		l2 = node;
		node.next = new ListNode(4);
		node = node.next;
		node.next = new ListNode(5);
		node = node.next;
		node.next = new ListNode(8);
		node = node.next;
		node.next = new ListNode(10);

		Main main = new Main();
		ListNode listNode = main.mergeTwoLists(l1, l2);
		while (listNode != null) {
			System.out.print(listNode.value + ", ");
			listNode = listNode.next;
		}
	}

	/* Solution of Merge Two Sorted Linked List */
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) return null;
		if(l1 == null && l2 != null) return l2;
		if(l1 != null && l2 == null) return l1;
		
		ListNode head = new ListNode(0);
		ListNode temp = head;
		
		while (l1 != null && l2 != null) {
			if (l1.value < l2.value) { 
                temp.next = l1; 
                temp = temp.next; 
                l1 = l1.next;
            } else if (l1.value > l2.value) {
				temp.next = l2;
				temp = temp.next;
				l2 = l2.next;
			} else {
				temp.next = l1;
				temp = temp.next;
				l1 = l1.next;
				temp.next = l2;
				temp = temp.next;
				l2 = l2.next;
			}
		}
        if(l1 != null){
            temp.next = l1;
        }else if(l2 != null){
            temp.next = l2;
        }
		return head.next;
    }

	/* Definition of Linked List Node */
	public static class ListNode {
		int value;
		ListNode next;
		public ListNode(int value) {
			this.value = value;
		}
	}
}

Result

1, 2, 3, 4, 5, 7, 8, 9, 10, 11,

Similar Post

1. Insert into a Binary Search Tree
2. Minimum Depth of Binary Tree
3. Find Largest Value in Each Tree Row

That’s all for Merge Two Sorted Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.