Abstract / Summary

Find the node where two linked lists meet.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 64% (3+ million submissions).

Typical patterns to solve this problem:

• Hash Table
• Linked List
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic problem of finding the first common node (intersection) of two singly-linked lists. It does so by traversing the first list, recording each visited node in a hash-based container, and then scanning the second list until a node that already exists in the container is encountered. If such a node is found, it is returned as the intersection point; otherwise the function returns None, indicating that the two lists do not intersect.

Key Steps

The algorithm can be broken down into three logical phases, each reflected directly in the source code.

Recording nodes of the first list

seen = set()

scan = headA
while scan:
    seen.add(scan)
    scan = scan.next

In this phase a set named seen is created to hold references to every node encountered while walking through list A. The loop continues until the end of the list (scan becomes None). Adding a node to a set stores the object’s identity, which later enables constant-time membership checks.

Searching for a matching node in the second list

scan = headB
while scan:
    if scan in seen:
        return scan
    scan = scan.next

Here the pointer scan is re-initialized to the head of list B. The loop iterates over each node of list B, testing whether the current node already resides in the seen set. The first occurrence of a node that is present in seen is the intersection point, and the function returns it immediately.

Handling the non-intersection case

return None

If the second loop exhausts list B without finding any node that appears in seen, the function reaches this final statement and returns None. This return value signals that the two input lists are disjoint.

Edge Cases Handled

The code gracefully deals with several boundary conditions without requiring explicit checks.

When either headA or headB is None, the corresponding while loop simply does not execute. If headA is None, the seen set remains empty, and the second loop will never find a match, leading to a None return. Conversely, if headB is None, the second loop is bypassed and the function also returns None. Thus, empty lists are correctly identified as having no intersection.

If the two lists intersect at the very first node (i.e., headA and headB reference the same object), the first loop adds that node to seen, and the second loop immediately detects the match on its first iteration, returning the head node as the intersection.

When the lists share a long tail after diverging early, the algorithm still records every node of the first list and then finds the first shared node while scanning the second list, ensuring the correct intersection point is returned regardless of where the merge occurs.

Performance Optimizations Observed

The primary optimization stems from the use of a hash-based set to store visited nodes. In Python, membership testing (node in seen) operates in average constant time, which makes the second traversal efficient even for long lists. By avoiding nested loops or repeated scans of the same list, the algorithm achieves a linear pass over each list exactly once.

Storing node references directly (rather than copying values) ensures that the memory footprint is minimal: each entry in the set is a pointer to an existing node, not a duplicate structure. This approach also leverages Python’s built-in memory management for hash tables, which is highly tuned for fast insertion and lookup.

The early return upon finding the intersection prevents unnecessary traversal of the remainder of list B. As soon as the first common node is detected, the function exits, saving cycles that would otherwise be spent iterating through the rest of the list.

Overall, the combination of a single pass to build the hash set, a single pass to locate the intersection, and immediate termination upon success yields an implementation that scales linearly with the total number of nodes across both lists while keeping auxiliary storage proportional only to the size of the first list.

Imagine two long trains parked on different tracks, and both trains eventually join together to form a single path. To find where the tracks merge, think of a group of friends holding onto a special list of all the train cars they have seen.

First, walk along the entire length of the first train from start to finish. Every time a new car is passed, add it to the list of seen cars. Once the end of the first train is reached, start walking along the second train from its beginning. As each car of the second train is passed, check if that specific car is already in the list of seen cars. The very first car that is found to be on both lists is the special spot where the two trains become one.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java							TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			JS	Go		Swift	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis						JS
	fartem								Ruby
	FelixFan1122				C#
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost							Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	muhammadfarhankt							Go
	qiyuangong		Python
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02					C
	vthwang			Java
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Swift, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
MacJim	C++
muhammadfarhankt	Go
qiyuangong	Python
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality