Intersection of Two Linked Lists

easy linked list two pointers

Problem

Return the node where two singly linked lists intersect, or null if they don't. Use O(1) extra space and O(m + n) time.

InputA = 1 → 9 → 1 → 2 → 4 ; B = 3 → 2 → 4 ; intersect at node "2"

Outputnode with value 2

If pA hits null, jump to headB; do the same with pB. After at most A + B steps they line up or both reach null.

list A unique prefix

list B unique prefix

shared tail

def getIntersectionNode(headA, headB):
    pA, pB = headA, headB
    while pA is not pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

function getIntersectionNode(headA, headB) {
  let pA = headA, pB = headB;
  while (pA !== pB) {
    pA = pA ? pA.next : headB;
    pB = pB ? pB.next : headA;
  }
  return pA;
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* pA = headA;
        ListNode* pB = headB;
        while (pA != pB) {
            pA = pA ? pA->next : headB;
            pB = pB ? pB->next : headA;
        }
        return pA;
    }
};

Explanation

Two lists may share a common tail. The challenge is finding where they merge using no extra memory and without knowing their lengths up front. The clever fix is a two-pointer switcheroo.

Walk pA through list A and pB through list B at the same pace. The catch: when pA runs off the end of A, it restarts at the head of B; when pB runs off B, it restarts at the head of A. That is exactly what pA = pA.next if pA else headB does.

Why does this line them up? Each pointer ends up walking A + B nodes total before stopping. Pointer A travels (length of A's unique part) + (shared part) + (length of B's unique part); pointer B travels the mirror image. Since both totals are equal, after that many steps they arrive at the same node — the intersection.

If the lists never intersect, both pointers eventually become null at the same time, so the loop ends with pA == pB == null and we correctly return null.

Example: A = 1 → 9 → 1 → 2 → 4, B = 3 → 2 → 4, sharing the 2 → 4 tail. After each pointer has walked all 5 + 3 nodes (with one head-swap each), they both land on the node with value 2, which is the answer.

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