Day 3 - Merge Two Sorted Lists

Refer others and earn a resume review from an experienced dev!

🧩 Problem:

You’re given the heads of two sorted linked lists: list1 and list2.

Your task?
Merge them into one sorted linked list, made by splicing together nodes from both lists.

Return the head of the new list.

🔍 Examples:

Example 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2
Input: list1 = [], list2 = []
Output: []

Example 3
Input: list1 = [], list2 = [0]
Output: [0]

📏 Constraints:

• Number of nodes in both lists: 0 <= n <= 50

• Node values range: -100 <= val <= 100

• Both list1 and list2 are already sorted in non-decreasing order

🧠 How to Approach It

This one is all about pointer manipulation — no fancy tricks, just careful list surgery.

Start by creating a dummy node to act as the head of your merged list. Use a pointer (cur) to track the current node as you walk through list1 and list2.

At each step:

• Compare the values at the head of both lists

• Append the smaller one to your merged list

• Move that list’s pointer forward

Once one list is empty, just tack on the rest of the other list — it’s already sorted!

✅ Python Solution:

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy

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

        # Attach the remaining elements
        cur.next = list1 if list1 else list2

        return dummy.next

🧵 TL;DR:

• 🧠 Use a dummy head to simplify pointer logic

• 🔁 Walk through both lists comparing nodes

• ⛓️ Splice together the smaller values

• 🧩 Clean and elegant — exactly what linked lists are for