Merge Two Sorted Linked Lists

Problem Statement:
Given two sorted linked lists, merge them into a single sorted linked list and return its head.

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

Approach:
We use two pointers to traverse both lists. At each step, we compare the current nodes and attach the smaller one to the result list. We continue this until one list is exhausted, then attach the remaining nodes.

Code:

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

def mergeTwoLists(list1, list2):
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

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

return dummy.next

Explanation:
The algorithm builds a new sorted list by comparing nodes from both lists. A dummy node is used to simplify handling of the head.

Time Complexity:
O(n + m), where n and m are lengths of lists

Space Complexity:
O(1), no extra space used