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]

Solution:

For this problem, my goal was to understand how linked lists work and learn how to traverse two lists at the same time while maintaining sorted order. I also wanted to avoid using extra space and keep the approach simple.

I used a two-pointer approach to merge both linked lists. The idea is to compare nodes from both lists, attach the smaller one to the result list, and move that pointer forward. This continues until one of the lists becomes empty, and then I just attach the remaining nodes at the end.

---

Solution Code:

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

A dummy node is used to make building the merged list easier, and a pointer is used to keep track of the current position. While traversing both lists, the smaller value is picked each time and added to the result, and that list’s pointer moves forward. Once one list is finished, the remaining nodes from the other list are directly attached.