Python Program to Merge Two Sorted Linked Lists

You can merge two sorted linked lists in Python by comparing their nodes one by one and linking the smaller node to the merged list using a helper function like mergeTwoLists(l1, l2) that returns the head of the merged sorted list.

Examples

Inputl1 = 1 -> 3 -> 5, l2 = 2 -> 4 -> 6

Output1 -> 2 -> 3 -> 4 -> 5 -> 6

Inputl1 = 1 -> 2 -> 4, l2 = 1 -> 3 -> 4

Output1 -> 1 -> 2 -> 3 -> 4 -> 4

Inputl1 = None, l2 = 0 -> 1

Output0 -> 1

How to Think About It

To merge two sorted linked lists, start from the heads of both lists and compare their values. Attach the smaller value node to a new merged list and move that list's pointer forward. Repeat this until one list is empty, then attach the remaining nodes of the other list to the merged list.

Algorithm

1

Create a dummy node to start the merged list.

2

Use a pointer to track the current end of the merged list.

3

While both lists have nodes, compare their current nodes.

4

Attach the smaller node to the merged list and move that list's pointer forward.

5

After the loop, attach any remaining nodes from either list.

6

Return the merged list starting after the dummy node.

Code

python

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

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    current = dummy
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 if l1 else l2
    return dummy.next

# Helper to print list

def printList(node):
    while node:
        print(node.val, end=' -> ' if node.next else '')
        node = node.next
    print()

# Example usage
l1 = ListNode(1, ListNode(3, ListNode(5)))
l2 = ListNode(2, ListNode(4, ListNode(6)))
merged = mergeTwoLists(l1, l2)
printList(merged)

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6

Dry Run

Let's trace merging l1 = 1 -> 3 -> 5 and l2 = 2 -> 4 -> 6 through the code

1

Initialize dummy and current

dummy = ListNode(0), current points to dummy

2

Compare l1.val=1 and l2.val=2

1 < 2, attach l1 node (1), move l1 to 3

3

Compare l1.val=3 and l2.val=2

2 < 3, attach l2 node (2), move l2 to 4

4

Compare l1.val=3 and l2.val=4

3 < 4, attach l1 node (3), move l1 to 5

5

Compare l1.val=5 and l2.val=4

4 < 5, attach l2 node (4), move l2 to 6

6

Compare l1.val=5 and l2.val=6

5 < 6, attach l1 node (5), move l1 to None

7

l1 is None, attach remaining l2 nodes

Attach l2 node (6)

Current merged list
0(dummy) -> 1
0(dummy) -> 1 -> 2
0(dummy) -> 1 -> 2 -> 3
0(dummy) -> 1 -> 2 -> 3 -> 4
0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5
0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

Why This Works

Step 1: Use a dummy node

The dummy node helps start the merged list easily without extra checks for the head.

Step 2: Compare nodes one by one

At each step, compare the current nodes of both lists and attach the smaller one to keep the merged list sorted.

Step 3: Attach remaining nodes

When one list ends, attach the rest of the other list because it is already sorted.

Alternative Approaches

Recursive merge

python

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

This method uses recursion to merge lists, which is elegant but uses extra call stack space.

Create new list with values

python

def mergeTwoLists(l1, l2):
    vals = []
    while l1:
        vals.append(l1.val)
        l1 = l1.next
    while l2:
        vals.append(l2.val)
        l2 = l2.next
    vals.sort()
    dummy = ListNode()
    current = dummy
    for v in vals:
        current.next = ListNode(v)
        current = current.next
    return dummy.next

This approach collects all values, sorts them, and creates a new list; simpler but less efficient.

Complexity: O(n + m) time, O(1) space

Time Complexity

The algorithm visits each node from both lists once, so the time is proportional to the total number of nodes.

Space Complexity

It uses only a few pointers and modifies the lists in place, so extra space is constant.

Which Approach is Fastest?

The iterative method with a dummy node is fastest and uses least memory compared to recursion or creating a new list.

Approach	Time	Space	Best For
Iterative with dummy node	O(n + m)	O(1)	Efficient in-place merging
Recursive merge	O(n + m)	O(n + m)	Cleaner code but uses call stack
Collect and sort values	O((n + m) log(n + m))	O(n + m)	Simple but less efficient