Merge Two Sorted Lists - CA15

My Thinking and Approach

---

Introduction

In this problem, I was given two sorted linked lists and asked to merge them into a single sorted linked list.

The final list should also be sorted.

---

Problem Statement

• Given two sorted linked lists list1 and list2

• Merge them into one sorted linked list

• Return the head of the merged list

• Conditions:

  • Use existing nodes
  • Maintain sorted order

---

My Initial Thought

At first, I considered:

• Converting both lists into arrays
• Merging arrays
• Rebuilding the linked list

But this approach uses extra space.

---

Key Observation

Since both lists are already sorted:

• I can compare nodes one by one
• Attach the smaller node to the result

---

Optimized Approach

I decided to merge the lists using pointer manipulation.

Logic:

• Compare current nodes of both lists
• Attach smaller node to result
• Move forward in that list

---

My Approach (Step-by-Step)

1. Create a dummy node

2. Use a pointer curr for result list

3. While both lists are not empty:

• Compare values
• Attach smaller node
• Move pointer forward

1. Attach remaining nodes of any list

2. Return dummy.next

---

Code (Python)

Below is the implementation clearly separated inside a code block:

```python id="k4p9zs"
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

class Solution:
def mergeTwoLists(self, list1, list2):
dummy = ListNode()
curr = dummy

    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next

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

    return dummy.next

---

## Example Walkthrough

### Input:



```text id="x2n9rf"
list1 = [1, 2, 4], list2 = [1, 3, 4]

Steps:

• Compare nodes and attach smaller values
• Continue until one list ends
• Attach remaining elements

Output:

```text id="v5k3qp"
[1, 1, 2, 3, 4, 4]

---

## Complexity Analysis

| Type             | Complexity |
| ---------------- | ---------- |
| Time Complexity  | O(n + m)   |
| Space Complexity | O(1)       |

---

## Key Takeaways

* Two pointer technique is effective
* No extra space required
* Dummy node simplifies implementation

---

## Conclusion

This problem helped me understand how to efficiently merge two sorted linked lists using pointer manipulation.

---