![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Merge Two Sorted Linked Lists
Problem Statement
1Problem Description :2 Given two sorted singly linked lists, merge them into a singly sorted linked list.345Input:6 Argument 1 -> head pointer to the first linked list "list1".7 Argument 2 -> head pointer to the second linked list "list2"89Output:10 Return the head pointer of the merged singly sorted linked list.
1Example 1 :23 Input :4 list1 = 1 -> 3 -> 75 list2 = 2 -> 5 -> 8 -> 967 Output: 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 989 Explanation :10 Merging list1 and list2 will result in 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 9
1Example 2 :23 Input :4 list1 = 1 -> 3 -> 7 -> 10 -> 115 list2 = null67 Output: 1 -> 3 -> 7 -> 10 -> 1189 Explanation :10 If one list is null, then the other list is the result array
Solution
Using Two Pointers
Prerequisite
Algorithm
1Input : head1 and head2, head pointers of linked lists list1 and list2 respectively23Step 0: Initialize head and current pointers to some dummy node45Step 1: if head1.val < head2.val6 update current.next to head1,7 current to current.next and8 move head1 to one node ahead910Step 2: else11 update current.next to head2,12 current to current.next and13 move head2 to one node ahead1415Step 3: Repeat Step1 and Step 2 until either one list is null1617Step 4: If still head1 is not null,18 update current.next to head11920Step 5: else if still head2 is not null,21 update current.next to head22223Step 6: Remove the dummy head node by24 updating head to head.next25 (as head node initially we created a dummy node and marked it as head)2627Output : head pointer of the merged linked list.
Example Dry Run
Input : list1 = 1 -> 3 -> 7, list2 = 2 -> 5 -> 8 -> 9
Iteration 1:
head1.val = 1 and head2.val = 2 as 1 < 2 ,
- current.next = head1
- current = current.next
- head1 = head1.next
Iteration 2 :
head1.val = 3 and head2.val = 2 as 3 > 2,
- current.next = head2
- current = current.next
- head2=head2.next
Iteration 3:
head1.val = 3 and head2.val = 5 as 3 < 5,
- current.next = head1
- current = current.next
- head1 = head1.next
Iteration 4:
head1.val = 7 and head2.val = 5 as 7 > 5,
- current.next = head2
- current = current.next
- head2=head2.next
Iteration 5 :
head1.val = 7 and head2.val = 8 as 7 < 8,
- current.next = head1
- current = current.next
- head1 = head1.next
Output : 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 9
Code Implementation
- Java
- Python
- Cpp
1public class MergeTwoSortedLinkedLists {23 // list node class4 private class ListNode {5 int val;6 ListNode next;78 ListNode(int val){9 this.val = val;10 }11 }1213 // method to merge two sorted lists into single sorted list14 public ListNode mergeLists(ListNode head1, ListNode head2) {15 // create dummy head node, this helps to avoid null checks16 // this way we do target to create what should be the next for the current node17 ListNode head = new ListNode(-1);18 ListNode current = head;1920 // Iterate lists to create new node which is next node the current node21 while (head1 != null && head2 != null) {22 // if head1 data/val is lesser than head2 data/val23 if(head1.val < head2.val) {24 current.next = head1;25 // as head1 is processed, move head1 one step ahead26 head1 = head1.next;27 }else {28 current.next = head2;29 // as head2 is processed, move head2 one step ahead30 head2 = head2.next;31 }32 // move current to the newly created node33 current = current.next;34 }3536 // If Still head1 points to node which is not null37 if (head1 != null) {38 current.next = head1 ;39 }4041 // If Still head1 points to node which is not null42 if (head2 != null) {43 current.next = head2 ;44 }4546 // as head node pointed to some dummy node ,47 // head.next is our actual head of resulted linked list48 return head.next;49 }5051 // Helper method to construct a linkedList by giving array of values52 private ListNode constructList(int[] array) {53 // create dummy head node, this helps to avoid null checks54 ListNode head = new ListNode(-1);55 ListNode current = head;5657 for(int i=0 ; i<array.length; i++){58 current.next = new ListNode(array[i]);59 current = current.next;60 }61 // as head node pointed to some dummy node ,62 // head.next is our actual head of the linked list63 return head.next;64 }6566 // Helper method to print given linked list67 private void print(ListNode head) {68 StringBuilder sb = new StringBuilder();6970 while(head != null) {71 sb.append(head.val +" -> ");72 head = head.next;73 }74 sb.append("NULL");75 System.out.println(sb.toString());76 }7778 // Driver Method79 public static void main(String[] args) {80 MergeTwoSortedLinkedLists obj = new MergeTwoSortedLinkedLists();81 int[] a1 = {1, 3, 7};82 int[] a2 = {2, 5, 8, 9};83 ListNode head1 = obj.constructList(a1);84 ListNode head2 = obj.constructList(a2);85 ListNode head = obj.mergeLists(head1, head2);86 obj.print(head);8788 int[] a11 = {};89 int[] a21 = {2, 5, 8, 9};90 head1 = obj.constructList(a11);91 head2 = obj.constructList(a21);92 head = obj.mergeLists(head1, head2);93 obj.print(head);9495 int[] l1 = {1, 3, 7};96 int[] l2 = {};97 head1 = obj.constructList(l1);98 head2 = obj.constructList(l2);99 head = obj.mergeLists(head1, head2);100 obj.print(head);101 }102103104}
Complexity Analysis
- Time Complexity : O(m+n) where m is the length of list1 and n is the length of the list2
- Space Complexity : O(1), No extra space is used.