A HashSet remembers nodes you’ve already visited — turning “have I seen this?” into O(1).
Focus on recognizing:
“Intersection” / “visited before?” → store node references, not values
Pattern 1: Cycle Detection (HashSet Version)
Watch the walker drop each node into the set and bail the instant it revisits one — the cycle closes. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Intersection of Two Linked Lists
Find the node where two lists merge — compare a HashSet solution against the O(1)-space two-pointer switch.
Add every node of list A to a set, then walk list B; the first node already in the set (by identity, NOT value) is the intersection. Matching by value is a trap — only node identity counts.
1
set = {}
2
for node in A: set.add(node) // by REFERENCE
3
for node in B:
4
if node in set: return node
5
return null
1
p = A head; q = B head
2
while p != q:
3
p = p.next ?? B head // switch at own end
4
q = q.next ?? A head
5
return p // meet at intersection
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<>();
ListNode cur = head;
while (cur != null) {
if (!seen.add(cur)) // add() returns false if present
return true;
cur = cur.next;
}
return false;
}def has_cycle(head):
seen = set()
cur = head
while cur:
if cur in seen:
return True
seen.add(cur)
cur = cur.next
return Falsebool hasCycle(ListNode* head) {
unordered_set<ListNode*> seen;
ListNode* cur = head;
while (cur) {
if (!seen.insert(cur).second) // already present
return true;
cur = cur->next;
}
return false;
}function hasCycle(head) {
const seen = new Set();
let cur = head;
while (cur) {
if (seen.has(cur)) return true;
seen.add(cur);
cur = cur.next;
}
return false;
}O(1) space alternative exists (Floyd’s tortoise & hare) — mention it in interviews.
Compare node identity (
==), never.val— equal values are not the same node.
Pattern 2: Intersection of Two Lists
Store list A’s nodes, then walk B until the first match — that node is the merge point. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Intersection of Two Linked Lists
Find the node where two singly linked lists merge, or null if they don't.
Walk both lists; when a pointer hits the end, redirect it to the other head. After at most lenA+lenB steps both pointers sit the same distance from the merge and meet on the shared node (or both reach null together).
1
pA, pB at both heads
2
walk; on null switch to other head
3
they align after |lenA−lenB| steps
4
first equal NODE = intersection
Store list A’s nodes; the first B node found in the set is the intersection:
public ListNode getIntersectionNode(ListNode a, ListNode b) {
Set<ListNode> seen = new HashSet<>();
while (a != null) {
seen.add(a);
a = a.next;
}
while (b != null) {
if (!seen.add(b)) // b's node is in A's set
return b;
b = b.next;
}
return null;
}def get_intersection_node(a, b):
seen = set()
while a:
seen.add(a)
a = a.next
while b:
if b in seen: # b's node is in A's set
return b
b = b.next
return NoneListNode* getIntersectionNode(ListNode* a, ListNode* b) {
unordered_set<ListNode*> seen;
while (a) {
seen.insert(a);
a = a->next;
}
while (b) {
if (seen.count(b)) // b's node is in A's set
return b;
b = b->next;
}
return nullptr;
}function getIntersectionNode(a, b) {
const seen = new Set();
while (a) {
seen.add(a);
a = a.next;
}
while (b) {
if (seen.has(b)) return b; // b's node is in A's set
b = b.next;
}
return null;
}O(1)-space alternative: walk both to their ends, redirect the shorter… or use the two-pointer switch trick.
Pattern 3: Remove Duplicates From Sorted List
Sorted input means duplicates are adjacent: unlink in one pass. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Remove Duplicates From Sorted List
Drop repeated values from a sorted linked list, keeping one of each.
Because the list is sorted, duplicates are adjacent. Compare cur.val with cur.next.val; if equal, bypass the next node, otherwise advance. One pass.
1
cur = head
2
while cur.next:
3
if cur.val == cur.next.val:
4
cur.next = cur.next.next // unlink dup
5
else: cur = cur.next
No set needed for sorted input — compare neighbors:
// Sorted list — values version
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val)
cur.next = cur.next.next; // skip duplicate
else
cur = cur.next;
}
return head;
}
// UNSORTED list — need the set
public ListNode removeDuplicates(ListNode head) {
Set<Integer> seen = new HashSet<>();
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
while (prev.next != null) {
if (!seen.add(prev.next.val)) {
prev.next = prev.next.next; // drop repeat
} else {
prev = prev.next;
}
}
return dummy.next;
}def delete_duplicates(head):
# sorted list — values version
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next # skip duplicate
else:
cur = cur.next
return head
def remove_duplicates(head):
# unsorted list — need the set
seen = set()
dummy = ListNode(0, head)
prev = dummy
while prev.next:
if prev.next.val in seen:
prev.next = prev.next.next # drop repeat
else:
seen.add(prev.next.val)
prev = prev.next
return dummy.nextListNode* deleteDuplicates(ListNode* head) {
// sorted list — values version
ListNode* cur = head;
while (cur && cur->next) {
if (cur->val == cur->next->val)
cur->next = cur->next->next; // skip duplicate
else
cur = cur->next;
}
return head;
}
ListNode* removeDuplicates(ListNode* head) {
// unsorted list — need the set
unordered_set<int> seen;
ListNode dummy(0, head);
ListNode* prev = &dummy;
while (prev->next) {
if (seen.count(prev->next->val)) {
prev->next = prev->next->next; // drop repeat
} else {
seen.insert(prev->next->val);
prev = prev->next;
}
}
return dummy.next;
}function deleteDuplicates(head) {
// sorted list — values version
let cur = head;
while (cur && cur.next) {
if (cur.val === cur.next.val) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
}
function removeDuplicates(head) {
// unsorted list — need the set
const seen = new Set();
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next) {
if (seen.has(prev.next.val)) {
prev.next = prev.next.next; // drop repeat
} else {
seen.add(prev.next.val);
prev = prev.next;
}
}
return dummy.next;
}Sorted → neighbor comparison. Unsorted → the set earns its space.
Common Mistakes
Storing values instead of nodes.
[1,1] in two different lists are different nodes; value sets give wrong intersections.
Using hashing when Floyd’s suffices.
Cycle detection with a set costs O(n) space — know both answers.
Advancing cur after deletion.
After cur.next = cur.next.next, do NOT also advance — re-check the new neighbor.
Complexity
| Operation | Time | Space |
|---|---|---|
| Cycle detect | O(n) | O(n) |
| Intersection | O(m + n) | O(m) |
| Dedup sorted | O(n) | O(1) |
Premium Content
Unlock Linked List Hashing and all premium lessons with a subscription.
From ₹199.99/year — See plans