Master Python Linked List: Reverse and Merge Techniques Explained

Reverse Linked List

Reversing a linked list is a common operation in many scenarios, such as displaying time‑series data in reverse order, checking for palindrome lists, or performing image flips when data is stored as a linked list.

Iterative Method

The iterative approach traverses the list while redirecting each node's next pointer to its predecessor.

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

def list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

def linked_list_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# Test
input_list = [1, 2, 3, 4, 5]
head = list_to_linked_list(input_list)
reversed_head = reverseList(head)
output_list = linked_list_to_list(reversed_head)
print(output_list)  # Output: [5, 4, 3, 2, 1]

Recursive Method

The recursive approach first reverses the sub‑list after the current node, then links the current node after the reversed sub‑list.

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

def reverseList(head):
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

# Test (same as above)
input_list = [1, 2, 3, 4, 5]
head = list_to_linked_list(input_list)
reversed_head = reverseList(head)
output_list = linked_list_to_list(reversed_head)
print(output_list)  # Output: [5, 4, 3, 2, 1]

Both methods have O(n) time complexity; the iterative version uses O(1) extra space, while the recursive version uses O(n) stack space.

Merge Linked Lists

Merging sorted linked lists is essential for algorithms such as multi‑way merge sort, combining query results, or stitching audio/video streams.

Merge Two Sorted Lists

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

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    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
    if l1:
        current.next = l1
    if l2:
        current.next = l2
    return dummy.next

# Helper functions (same as above) and test
list1 = [1, 2, 4]
list2 = [1, 3, 4]
l1 = list_to_linked_list(list1)
l2 = list_to_linked_list(list2)
merged_head = mergeTwoLists(l1, l2)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # Output: [1, 1, 2, 3, 4, 4]

Merge K Sorted Lists (Divide and Conquer)

def mergeKLists(lists):
    if not lists:
        return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(mergeTwoLists(l1, l2) if l2 else l1)
        lists = merged
    return lists[0]

# Test with three lists
lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
linked_lists = [list_to_linked_list(lst) for lst in lists]
merged_head = mergeKLists(linked_lists)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # Output: [1, 1, 2, 3, 4, 4, 5, 6]

Handling Empty Lists When Merging

It is crucial to check for empty inputs to avoid AttributeError and to ensure correct logical flow.

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    if not l1:
        return l2
    if not l2:
        return l1
    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
    if l1:
        current.next = l1
    if l2:
        current.next = l2
    return dummy.next

# Test empty case
list1 = []
list2 = [1, 2, 3]
l1 = list_to_linked_list(list1)
l2 = list_to_linked_list(list2)
merged_head = mergeTwoLists(l1, l2)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # Output: [1, 2, 3]

By explicitly handling empty inputs at the start of the merge function, the code becomes more robust and avoids runtime crashes.