CA 15 - Merge two linked list

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Examples:

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

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

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

My Goal

For this problem, my goal was to:

Understand how linked lists work
Learn how to traverse two lists simultaneously
Merge elements while maintaining sorted order
Avoid using extra space as much as possible

Solution

I used a two-pointer approach to merge both linked lists.

Idea:

Compare nodes from both lists
Add the smaller node to the result list
Move that list’s pointer forward
Continue until one list is empty
Attach remaining nodes

Solution Code (Python)

class ListNode:
    def __init__(s, v=0, n=None):
        s.val = v
        s.next = n

def mergeTwoLists(a, b):
    d = ListNode()
    c = d

    while a and b:
        if a.val < b.val:
            c.next = a
            a = a.next
        else:
            c.next = b
            b = b.next
        c = c.next

    if a:
        c.next = a
    else:
        c.next = b

    return d.next

Explanation

Use a dummy node d to simplify list creation
c is the current pointer for the merged list
Compare values of both lists
Attach smaller node and move forward
At the end, attach remaining nodes