Merge Two Sorted Linked Lists

Problem Statement

You are given the heads of two sorted linked lists, list1 and list2. Your task is to merge the two lists into one sorted linked list by splicing together the nodes of the first two lists.

Return the head of the merged linked 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]

Approach

Create a dummy node to serve as the start of the merged list.
Use a pointer current to track the last node in the merged list.
Compare the nodes from both lists:
Append the smaller node to current.next.
Move the pointer of the list from which the node was taken.
Once one list is exhausted, append the remaining nodes from the other list.
Return dummy.next as the head of the merged list

Python Code

class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

class Solution:
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
dummy = ListNode(-1)
current = dummy

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

    # Append remaining nodes
    if list1:
        current.next = list1
    elif list2:
        current.next = list2

    return dummy.next