Merge Two Linked List

Problem Statement

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

Merge both lists into one sorted linked list by:

Splicing together the nodes of the two lists
Maintaining sorted order

Return the head of the merged linked list.

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, 50]
-100 <= Node.val <= 100
Both lists are sorted in non-decreasing order
Approach – Two Pointer Technique

Since both linked lists are already sorted:

Compare the current nodes of both lists
Attach the smaller node to the merged list
Move that pointer forward
Repeat until one list becomes empty
Attach the remaining nodes
Step-by-Step Logic
Create a dummy node (to simplify edge cases)
Maintain a pointer current
While both lists are not empty:
Compare values
Attach the smaller node
Move that list forward
Attach the remaining part of the non-empty list
Return dummy.next
Why Use a Dummy Node?

The dummy node:

Helps avoid special handling for the first element
Makes the logic clean and simple
Returns the actual head using dummy.next
Implementation (Iterative – Recommended)

Definition for singly-linked list.

class ListNode:

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

self.val = val

self.next = next

class Solution:
def mergeTwoLists(self, list1, list2):
dummy = ListNode(0)
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

    # Attach remaining nodes
    if list1:
        current.next = list1
    else:
        current.next = list2

    return dummy.next

Dry Run Example

For:

list1 = 1 → 2 → 4
list2 = 1 → 3 → 4

Comparisons:

1 and 1 → take first 1
2 and 1 → take second 1
2 and 3 → take 2
4 and 3 → take 3
4 and 4 → take 4
Remaining 4 → attach

Final list:

1 → 1 → 2 → 3 → 4 → 4
Time and Space Complexity

Time Complexity: O(n + m)
Where n and m are lengths of the two lists.

Space Complexity: O(1)
(No extra data structures used.)