# Merge Two Sorted Lists

Clarify the problem:

- The problem requires merging two sorted linked lists into a single sorted linked list.
- We need to return the head of the merged list.

Analyze the problem:

- Input: Two sorted linked lists, each represented by its head node.
- Output: The head of the merged sorted linked list.
- Constraints:
- The input linked lists can have 0 or more nodes.
- The nodes in each linked list are sorted in ascending order.

Design an algorithm:

- To solve the problem:
- Create a dummy node to serve as the head of the merged list.
- Initialize two pointers,
`curr`

and`prev`

, both pointing to the dummy node. - Iterate through both linked lists simultaneously until either one of them reaches the end.
- Compare the values of the nodes at the current positions of the two pointers.
- Move the pointer with the smaller value to its next node and update the
`curr`

pointer accordingly. - Continue the iteration until both linked lists have been traversed.
- Attach the remaining nodes (if any) of the non-empty linked list to the end of the merged list.
- Return the head of the merged list (i.e., the next node after the dummy node).

- To solve the problem:
Explain your approach:

- To merge two sorted linked lists, we start by creating a dummy node that will serve as the head of the merged list.
- We initialize two pointers,
`curr`

and`prev`

, both pointing to the dummy node. - Then, we iterate through both linked lists simultaneously until either one of them reaches the end.
- At each iteration, we compare the values of the nodes at the current positions of the two pointers.
- We move the pointer with the smaller value to its next node and update the
`curr`

pointer accordingly. - We continue this process until both linked lists have been traversed.
- Finally, we attach the remaining nodes (if any) of the non-empty linked list to the end of the merged list.
- We return the head of the merged list (i.e., the next node after the dummy node).

Write clean and readable code:

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# Create a dummy node as the head of the merged list
dummy = ListNode(0)
current = dummy
# Compare the values of the nodes in both lists and append the smaller one
# to the merged list
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# Append the remaining nodes of the non-empty list to the merged list
if list1:
current.next = list1
else:
current.next = list2
# Return the head of the merged list (excluding the dummy node)
return dummy.next
```

- Test your code:
- Test case 1:
- l1: 1 -> 2 -> 4
- l2: 1 -> 3 -> 4
- After merging the two lists, the resulting merged list should be: 1 -> 1 -> 2 -> 3 -> 4 -> 4.

- Test case 1:

python

```
# Test case 1
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)
merged_list = mergeTwoLists(l1, l2)
while merged_list:
print(merged_list.val, end=" ")
merged_list = merged_list.next
# Output: 1 1 2 3 4 4
```

- Test case 2:
- l1: 1 -> 2 -> 4
- l2: None
- After merging the two lists, the resulting merged list should be: 1 -> 2 -> 4.

python

```
# Test case 2
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l2 = None
merged_list = mergeTwoLists(l1, l2)
while merged_list:
print(merged_list.val, end=" ")
merged_list = merged_list.next
# Output: 1 2 4
```

Optimize if necessary:

- The provided solution already uses a two-pointer approach, which is the most efficient approach for merging two sorted lists.
- Therefore, there is no further optimization needed.

Handle error cases:

- The algorithm handles the case where either or both of the input linked lists are empty.
- If both linked lists are empty, the algorithm returns None.

Discuss complexity analysis:

- The time complexity of the algorithm is O(n + m), where n and m are the lengths of the two input linked lists.
- The algorithm performs a single pass through both linked lists, comparing the node values and merging them into a new list.
- The space complexity is O(1) since the algorithm only uses a constant amount of extra space to store the pointers.