AlgoViz
HomeLinked List

Find the intersection point of Y LL

Medium

Swap heads to equalise the walk

Problem

Given the heads of two linked lists A and B, containing positive integers. Find the node at which the two linked lists intersect. If they do intersect, return the node at which the intersection begins, otherwise return null. The Linked List will not contain any cycles. The linked lists must retain their original structure, given as per the input, after the function returns. Note: for custom input, the following parameters are required(your program is not provided with these parameters): intersectVal - The value of the node where the intersection occurs. This is -1 if there is no intersected node. skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node(-1 if no intersection). skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node(-1 if no intersection). listA - The first linked list. listB - The second linked list.

In simple words

Walk both lists to equal remaining length, then step together — they meet at the intersection.

The idea

Walk both lists, and when a pointer hits the end send it to the other list's head. Both pointers then travel the same total distance, so they arrive at the intersection together — or at null together if there is none.

The trick

  • Each pointer covers lenA + lenB, which is why they synchronise.
  • No cycle risk: each pointer switches lists exactly once.
  • O(n + m) time, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — Values: 0.

1/2
Optimal
timeO(n+m)spaceO(1)
1a = headA; b = headB2while a != b:3  a = a ? a.next : headB4  b = b ? b.next : headA5return a        // meeting node (or null)

Input

array
[0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
listA = 1->2->[8->4->5], listB = 6->[8->4->5]
Output:
8
Explanation:
Both lists join at node 8.

Example 2

Input:
listA = 3->[7], listB = 9->4->[7]
Output:
7
Explanation:
They meet at 7.

Example 3

Input:
listA = 1->2, listB = 3->4 (no join)
Output:
-1
Explanation:
No shared node → -1.

Constraints

  • m == number of nodes in listA.
  • n == number of nodes in listB.
  • 1 <= m, n <= 5 * 10^4
  • 0 <= ListNode.val <= 10^4
  • 0 <= skipA < m
  • 0 <= skipB < n
  • intersectVal, skipA, skipB is -1 if listA and listB do not intersect.
  • intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.