ASSIGNMENT 15

1. Merge Two Sorted Lists

Problem
Given two sorted linked lists, merge them into one sorted linked list.

Example:
Id="ex8"
Input:
a = 1 → 3 → 5

b = 2 → 4 → 6

Output:
1 → 2 → 3 → 4 → 5 → 6

**Approach Used: **Recursion
Instead of using loops, we:
Compare the current nodes
Attach the smaller one
Recursively merge the remaining list

CODE:

class Solution:
def mergeTwoLists(self, a, b):
if a and b:
if a.val > b.val:
a, b = b, a
a.next = self.mergeTwoLists(a.next, b)
return a or b

Core Idea (Most Important Part)
👉 Always pick the smaller node and connect it to the result
Then:
Move forward in that list
Keep the other list as it is
Repeat recursively

How recursion works here
Let’s say:

a = 1 → 3

b = 2 → 4

Step 1:
Compare 1 and 2 → pick 1
Now solve: merge(3, 2)

Step 2:
Compare 3 and 2 → pick 2
Now solve: merge(3, 4)

Step 3:
Compare 3 and 4 → pick 3

Continue...
👉 It keeps breaking the problem into smaller subproblems

Complexity Analysis
Time Complexity: O(n + m)
Space Complexity: O(n + m) ❗ (due to recursion stack)

Conclusion
Recursive solution is:
Elegant
Easy to write
Iterative solution is:
More practical for large data