Tagged
• DSA Problems
• Sorting
• Two Pointer Technique
•

# 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 -> 96
7  Output: 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 98
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 -> 115  list2 = null6
7  Output: 1 -> 3 -> 7 -> 10 -> 118
9  Explanation :10  If one list is null, then the other list is the result array```

# Using Two Pointers

## Algorithm

```1Input : head1 and head2, head pointers of linked lists list1 and list2 respectively2
3Step 0: Initialize head and current pointers to some dummy node4
10Step 2: else 11        update current.next to head2, 12        current to current.next and13        move head2 to one node ahead14
15Step 3: Repeat Step1 and Step 2 until either one list is null16
17Step 4: If still head1 is not null, 18        update current.next to head119
20Step 5: else if still head2 is not null, 21        update current.next to head222
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

## 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 = current.next

• Iteration 2 :

• current = current.next

• Iteration 3:

• current = current.next

• Iteration 4:

• current = current.next

• Iteration 5 :

• current = current.next

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

## Code Implementation

1. Java
2. Python
3. Cpp

```1public class MergeTwoSortedLinkedLists {2
3    // list node class4    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 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;19
36        // If Still head1 points to node which is not null37        if (head1 != null) {38            current.next = head1 ;39        }40
41        // If Still head1 points to node which is not null42        if (head2 != null) {43            current.next = head2 ;44        }45
51    // 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;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 list63        return head.next;64    }65
66    // Helper method to print given linked list67    private void print(ListNode head) {68        StringBuilder sb = new StringBuilder();69
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