Intersection of Two Linked Lists Easy 0 attempts
LeetCode ↗

Intersection of Two Linked Lists

Easy Linked List LeetCode

You're given the heads of two singly linked lists, headA and headB, which may merge into a shared tail at some point. Find and return the exact node where they come together, or null if they never do. Neither list may be modified in the process — both must look the same after your function returns — and you're guaranteed neither list loops back on itself anywhere.

Input Format
Implement intersectionOfTwoLinkedLists(headA, headB). Inputs below show JavaScript function arguments; there is no stdin parsing. listFixture is [prefixA, prefixB, sharedTail]. The editor builds two list heads that share the same tail nodes.
Output Format
Return the result described in the statement. Return the intersection node itself; the editor displays its value or null.

Sample Input and Output

Example 1 · Run Sample

Input
listFixture = [[4,1],[5,6,1],[8,4,5]]
Output
8

Example 2

Input
listFixture = [[1],[2],[]]
Output
null
Constraints
  • 0 <= length of either list <= 3 * 10^4
  • 1 <= node.val <= 10^5
  • Lists are acyclic; intersection means shared node identity, not equal values.
Test Cases (2)
Case 1
Args: [[[4,1],[5,6,1],[8,4,5]]] Expected: 8
Case 2
Args: [[[1],[2],[]]] Expected: null
Topics
Linked List

Approach: Two Pointers

Use two pointers, one starting at each head. When a pointer reaches the end of its list, redirect it to the head of the other list. Both pointers travel the same total distance, so they will meet at the intersection node, or both reach null if there is no intersection.

javascript
function intersectionOfTwoLinkedLists(headA, headB) {
  let a = headA, b = headB;
  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
  return a;
}

Time Complexity: O(m + n)

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript