Merge Two Sorted Linked Lists

Problem Statement

1Problem Description :
2  Given two sorted singly linked lists, merge them into a singly sorted linked list.
3
4
5Input: 
6  Argument 1 -> head pointer to the first linked list "list1".
7  Argument 2 -> head pointer to the second linked list "list2"
8
9Output:
10  Return the head pointer of the merged singly sorted linked list.

1Example 1 :
2
3  Input : 
4    list1 = 1 -> 3 -> 7 
5    list2 = 2 -> 5 -> 8 -> 9
6
7  Output: 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 9
8
9  Explanation :
10    Merging list1 and list2 will result in 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 9

1Example 2 :
2
3  Input : 
4  list1 = 1 -> 3 -> 7 -> 10 -> 11
5  list2 = null
6
7  Output: 1 -> 3 -> 7 -> 10 -> 11
8
9  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 respectively
2
3Step 0: Initialize head and current pointers to some dummy node
4
5Step 1: if head1.val < head2.val 
6        update current.next to head1, 
7        current to current.next and 
8        move head1 to one node ahead 
9
10Step 2: else 
11        update current.next to head2, 
12        current to current.next and
13        move head2 to one node ahead
14
15Step 3: Repeat Step1 and Step 2 until either one list is null
16
17Step 4: If still head1 is not null, 
18        update current.next to head1
19
20Step 5: else if still head2 is not null, 
21        update current.next to head2
22
23Step 6: Remove the dummy head node by 
24        updating head to head.next 
25        (as head node initially we created a dummy node and marked it as head)
26
27Output : head pointer of the merged linked list.

Example Dry Run

Input : list1 = 1 -> 3 -> 7, list2 = 2 -> 5 -> 8 -> 9

Initialize head and current pointers to some dummy node

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

As head1 points to null and head2 is not null,
- update current.next = head2

Now remove dummy node by updating head = head.next

Output : 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 9

Code Implementation

Java
Python
Cpp

1public class MergeTwoSortedLinkedLists {
2
3    // list node class
4    private class ListNode {
5        int val;
6        ListNode next;
7
8        ListNode(int val){
9            this.val = val;
10        }
11    }
12
13    // method to merge two sorted lists into single sorted list
14    public ListNode mergeLists(ListNode head1, ListNode head2) {
15        // create dummy head node, this helps to avoid null checks
16        // this way we do target to create what should be the next for the current node
17        ListNode head = new ListNode(-1);
18        ListNode current = head;
19
20        // Iterate lists to create new node which is next node the current node
21        while (head1 != null && head2 != null) {
22            // if head1 data/val is lesser than head2 data/val
23            if(head1.val < head2.val) {
24                current.next = head1;
25                // as head1 is processed, move head1 one step ahead
26                head1 = head1.next;
27            }else {
28                current.next = head2;
29                // as head2 is processed, move head2 one step ahead
30                head2 = head2.next;
31            }
32            // move current to the newly created node
33            current = current.next;
34        }
35
36        // If Still head1 points to node which is not null
37        if (head1 != null) {
38            current.next = head1 ;
39        }
40
41        // If Still head1 points to node which is not null
42        if (head2 != null) {
43            current.next = head2 ;
44        }
45
46        // as head node pointed to some dummy node ,
47        // head.next is our actual head of resulted linked list
48        return head.next;
49    }
50
51    // Helper method to construct a linkedList by giving array of values
52    private ListNode constructList(int[] array) {
53        // create dummy head node, this helps to avoid null checks
54        ListNode head = new ListNode(-1);
55        ListNode current = head;
56
57        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 list
63        return head.next;
64    }
65
66    // Helper method to print given linked list
67    private void print(ListNode head) {
68        StringBuilder sb = new StringBuilder();
69
70        while(head != null) {
71            sb.append(head.val +" -> ");
72            head = head.next;
73        }
74        sb.append("NULL");
75        System.out.println(sb.toString());
76    }
77
78    // Driver Method
79    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);
87
88        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);
94
95        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    }
102
103
104}

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.

DSA Problems

Sorting

Linked List

Two Pointer Technique

String Reverse

Remove Duplicates From Sorted List

...