Merging Linked Lists

Tags

Merging Linked Lists

Category

Linked Lists

Difficulty

Medium

Problem Statement

Given two singly linked lists that may or may not intersect (share a common tail), find the intersection node where the two lists merge into one. If the lists do not intersect, return null. The intersection is defined by reference (the same node object), not by value.

Intuition

If two linked lists intersect, they share a common tail. The key challenge is that the lists may have different lengths, so corresponding nodes are offset. By calculating the length difference and advancing the pointer on the longer list by that difference, we align both pointers so they reach the intersection node at the same step.

Alternatively, a two-pointer technique works elegantly: when one pointer reaches the end of its list, redirect it to the head of the other list. Both pointers will traverse the same total distance (lengthA + lengthB), and they will meet at the intersection node (or both reach null simultaneously if there is no intersection).

Approach

  1. Initialize two pointers, one at each list's head.
  2. Traverse both lists simultaneously: a. If a pointer reaches null, redirect it to the head of the other list. b. Otherwise, advance it one step.
  3. When the two pointers meet (point to the same node), that node is the intersection.
  4. If both reach null, the lists do not intersect.

Pseudocode

function findIntersection(headA, headB):
    if headA is null or headB is null:
        return null
    pointerA = headA
    pointerB = headB

    while pointerA != pointerB:
        pointerA = pointerA.next if pointerA is not null else headB
        pointerB = pointerB.next if pointerB is not null else headA

    return pointerA  // either the intersection node or null

Time & Space Complexity

  • Time: O(n + m), where n and m are the lengths of the two lists. Each pointer traverses at most n + m nodes.
  • Space: O(1). Only two pointers are used regardless of input size.

Key Insights

  • The two-pointer redirect trick works because both pointers travel the same total distance: lengthA + lengthB. If the lists intersect, the pointers synchronize at the intersection node.
  • If the lists do not intersect, both pointers will reach null at the same time (after traversing lengthA + lengthB nodes).
  • This problem tests reference equality, not value equality: two nodes with the same value at different memory locations do not count as an intersection.
  • An alternative approach using a hash set (store all nodes from one list, check against the other) uses O(n) space.

Edge Cases

  • One or both lists are empty: return null.
  • The lists are identical (same head): the head itself is the intersection.
  • The lists do not intersect at all: return null.
  • The intersection is at the very last node of both lists.
  • One list is much longer than the other.

Linked mentions