Merge Two Linked List

Introduction

Linked Lists are a fundamental data structure in computer science.
A common problem is merging two sorted linked lists into one sorted list.

This problem helps in understanding pointer manipulation and is frequently asked in interviews.

Problem Statement

You are given two sorted linked lists list1 and list2.

Task:
Merge them into a single sorted linked list and return its head.

Conditions:

• Lists are already sorted
• Merge should be done by rearranging nodes (not creating new list unnecessarily)

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]

Intuition

• Compare nodes from both lists
• Pick the smaller value
• Move forward

This is similar to the merge step in merge sort

Approach

We use a dummy node to simplify handling.

Algorithm Steps

• Create a dummy node
• Use a pointer current

• Compare nodes from both lists:

  • Attach smaller node to result
  • Move that list forward

• When one list ends:

  • Attach remaining part of the other list

• Return dummy.next

Code (Python)

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

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

    return dummy.next

Step-by-Step Explanation

For:
[1 → 2 → 4] and [1 → 3 → 4]

• Compare 1 and 1 → pick one
• Compare 2 and 1 → pick 1
• Compare 2 and 3 → pick 2
• Continue until done

Final → [1 → 1 → 2 → 3 → 4 → 4]

Complexity Analysis

• Time Complexity: O(n + m)
• Space Complexity: O(1)

Conclusion

Merging two sorted linked lists is a fundamental problem that teaches efficient pointer handling and merging logic.