Merge Two Sorted Lists

Merge Two Sorted Lists
Problem Statement

We are given two sorted linked lists and we need to merge them into one sorted linked list and return the head of the merged list.

Example
Input:
List1 = 1 -> 2 -> 4
List2 = 1 -> 3 -> 4

Output:
1 -> 1 -> 2 -> 3 -> 4 -> 4
Understanding the Problem

Since both linked lists are already sorted, we can merge them similarly to the merge step in Merge Sort.

We compare nodes from both lists and attach the smaller one to the result list.

Approach 1: Iterative Method
Idea
Create a dummy node
Compare nodes from list1 and list2
Attach smaller node to result
Move that list pointer forward
Continue until one list ends
Attach remaining list

Step-by-Step Algorithm
Create dummy node
Set pointer = dummy
While both lists not empty:
If list1.val < list2.val → attach list1
Else attach list2
Attach remaining nodes
Return dummy.next

Python Code
class Node:
def init(self, data):
self.data = data
self.next = None

def mergeTwoLists(list1, list2):
dummy = Node(0)
current = dummy

while list1 and list2:
    if list1.data <= list2.data:
        current.next = list1
        list1 = list1.next
    else:
        current.next = list2
        list2 = list2.next

    current = current.next

if list1:
    current.next = list1
else:
    current.next = list2

return dummy.next

def printList(head):
while head:
print(head.data, end=" -> ")
head = head.next
print("None")

Create List1: 1 -> 2 -> 4

list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(4)

Create List2: 1 -> 3 -> 4

list2 = Node(1)
list2.next = Node(3)
list2.next.next = Node(4)

merged = mergeTwoLists(list1, list2)
printList(merged)

Approach 2: Recursion Method

Idea
Compare first nodes
Smaller node becomes head
Recursively merge remaining lists

Python Code
def mergeTwoLists(list1, list2):
if not list1:
return list2
if not list2:
return list1

if list1.data < list2.data:
    list1.next = mergeTwoLists(list1.next, list2)
    return list1
else:
    list2.next = mergeTwoLists(list1, list2.next)
    return list2

Complexity Analysis
Type Complexity
Time O(n + m)
Space O(1) iterative
Space O(n) recursive

Where:

n = length of list1
m = length of list2

Summary
Method Time Space
Iterative O(n+m) O(1)
Recursion O(n+m) O(n)

Best Method → Iterative Method

Conclusion

To merge two sorted linked lists:

Compare nodes from both lists
Attach smaller node
Move pointer
Continue until lists end
Attach remaining nodes

This problem is very important and also used in Merge Sort for Linked List.