Intersection of Two Linked Lists Easy 0 attempts
LeetCode ↗

Intersection of Two Linked Lists

Easy Linked List LeetCode

Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection, return null. The linked lists must retain their original structure after the function returns. There are no cycles anywhere in the entire linked structure.

Example:

Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], intersection at node with value 8
Output: Node with value 8
Sample Input
—
Sample Output
—
Constraints
  • m + n nodes total
  • 1 <= Node.val <= 10^5
  • 0 <= skipA <= m, 0 <= skipB <= n
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.

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