Intersection Point of Two Linked Lists in DSA C#

Mental Model

Two linked lists may share some nodes at the end, forming a common tail. The intersection point is the first shared node.

Analogy: Imagine two roads that start separately but merge into one road at some point. The merge point is the intersection where both roads become the same path.

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
                      ↑
List B:       9 -> 8 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: List A: 1->2->3->4->5, List B: 9->8->4->5 (4 and 5 are shared nodes)

Goal: Find the first node where both lists intersect (node with value 4).

Step 1: Calculate lengths of both lists: lenA=5, lenB=4

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
List B: 9 -> 8 -> 4 -> 5 -> null

Why: Knowing lengths helps align both lists to compare nodes at the same distance from the end.

Step 2: Advance pointer in longer list (List A) by difference (1 step)

List A pointer at node 2 -> 3 -> 4 -> 5 -> null
List B pointer at node 9 -> 8 -> 4 -> 5 -> null

Why: Align both pointers so they have equal nodes left to traverse.

Step 3: Move both pointers forward together until they meet

Pointers at nodes 2 and 9 (not equal)
Pointers at nodes 3 and 8 (not equal)
Pointers at nodes 4 and 4 (equal)

Why: When pointers are equal, intersection is found.

Result:

Intersection at node with value 4
List A: 1 -> 2 -> 3 -> [4] -> 5 -> null
List B: 9 -> 8 -> [4] -> 5 -> null

Annotated Code

DSA C#

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = GetLength(headA);
        int lenB = GetLength(headB);

        // Align start of both lists
        while (lenA > lenB) {
            headA = headA.next; // advance longer list pointer
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next; // advance longer list pointer
            lenB--;
        }

        // Move both pointers until intersection or end
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA; // intersection found
            }
            headA = headA.next; // advance both pointers
            headB = headB.next;
        }
        return null; // no intersection
    }

    private int GetLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next; // traverse list to count nodes
        }
        return length;
    }
}

public class Program {
    public static void Main() {
        // Shared nodes
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4, node5);

        // List A: 1->2->3->4->5
        ListNode headA = new ListNode(1, new ListNode(2, new ListNode(3, node4)));

        // List B: 9->8->4->5
        ListNode headB = new ListNode(9, new ListNode(8, node4));

        Solution sol = new Solution();
        ListNode intersection = sol.GetIntersectionNode(headA, headB);

        if (intersection != null) {
            Console.WriteLine("Intersection at node with value " + intersection.val);
        } else {
            Console.WriteLine("No intersection");
        }
    }
}

int lenA = GetLength(headA); int lenB = GetLength(headB);

Calculate lengths of both lists to find difference

while (lenA > lenB) { headA = headA.next; lenA--; }

Advance pointer in longer list to align both lists

while (lenB > lenA) { headB = headB.next; lenB--; }

Advance pointer in longer list to align both lists

while (headA != null && headB != null) { if (headA == headB) return headA; headA = headA.next; headB = headB.next; }

Traverse both lists together to find intersection node

Output

Intersection at node with value 4

Complexity Analysis

Time: O(m + n) because we traverse both lists to get lengths and then traverse aligned parts once

Space: O(1) because we use only pointers and counters, no extra data structures

vs Alternative: Naive approach compares every node of one list with every node of the other, O(m*n), which is much slower

Edge Cases

One or both lists are empty

Returns null immediately since no intersection is possible

DSA C#

while (headA != null && headB != null) { ... }

Lists do not intersect

Returns null after traversing both lists fully

DSA C#

return null; // no intersection

Intersection at head node (both lists are the same)

Returns head node immediately

DSA C#

if (headA == headB) return headA;

When to Use This Pattern

When you see two linked lists and need to find if they share nodes, use the intersection point pattern by aligning lengths and traversing together.

Common Mistakes

Mistake: Comparing node values instead of node references to find intersection
Fix: Compare nodes by reference (headA == headB), not by value

Mistake: Not aligning the longer list pointer before traversal
Fix: Calculate lengths and advance the longer list pointer by the difference first

Summary

Finds the first shared node where two linked lists intersect.

Use when you need to detect if two linked lists merge and find the merge point.

Align both lists by length difference, then traverse together to find the intersection.

Practice

1. What does the "Intersection Point of Two Linked Lists" problem ask you to find?

easy

A. The node where two linked lists merge or start sharing nodes

B. The length of the longer linked list

C. The sum of all node values in both lists

D. The last node of the first linked list

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the node where two linked lists merge or start sharing nodes, meaning they have a common reference from that node onward.

2. Step 2: Differentiate from other concepts

   It is not about length, sum, or last node alone, but about the exact node where both lists intersect.

3. Final Answer:

   The node where two linked lists merge or start sharing nodes -> Option A

4. Quick Check:

   Intersection means shared node = A [OK]

Hint: Look for the first common node reference in both lists [OK]

Common Mistakes:

• Confusing intersection with equal values instead of shared nodes
• Thinking intersection means same length
• Looking for sum or last node instead of merge point

2. Which of the following C# code snippets correctly declares a singly linked list node class for this problem?

easy

A. class Node { int val; Node next; Node(int x) { val = x; next = null; } }

B. public class ListNode { int val; ListNode next; ListNode() { val = 0; next = null; } }

C. public struct ListNode { int val; ListNode next; }

D. public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } }

Solution

1. Step 1: Check for correct access modifiers and constructor

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } uses public fields and a constructor that initializes value and next pointer properly.

2. Step 2: Identify issues in other options

   class Node { int val; Node next; Node(int x) { val = x; next = null; } } lacks public keyword, so fields are private by default; public struct ListNode { int val; ListNode next; } uses struct which is not typical for linked lists; public class ListNode { int val; ListNode next; ListNode() { val = 0; next = null; } } has no constructor parameter and fields are private.

3. Final Answer:

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } -> Option D

4. Quick Check:

   Public class with constructor = B [OK]

Hint: Use public fields and constructor with parameter for node value [OK]

Common Mistakes:

• Omitting public keyword causing access issues
• Using struct instead of class for nodes
• Not initializing next pointer to null

3. What will be the output of the following C# code snippet that finds the intersection point of two linked lists? public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } public class Solution { public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { ListNode a = headA, b = headB; while (a != b) { a = (a == null) ? headB : a.next; b = (b == null) ? headA : b.next; } return a; } } // Setup lists ListNode common = new ListNode(8); common.next = new ListNode(10); ListNode headA = new ListNode(3); headA.next = new ListNode(7); headA.next.next = common; ListNode headB = new ListNode(99); headB.next = common; Solution sol = new Solution(); ListNode result = sol.GetIntersectionNode(headA, headB); Console.WriteLine(result.val);

medium

A. 99

B. 8

C. 7

D. 10

Solution

1. Step 1: Understand the linked list setup

   List A: 3 -> 7 -> 8 -> 10; List B: 99 -> 8 -> 10. The intersection node is the node with value 8.

2. Step 2: Trace the GetIntersectionNode method

   Two pointers traverse lists; when one reaches end, it switches to the other list head. They meet at intersection node 8.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Intersection node value = 8 [OK]

Hint: Pointers switch lists to align lengths and meet at intersection [OK]

Common Mistakes:

• Confusing node values instead of node references
• Assuming intersection is last node always
• Not switching pointers to other list head

4. Identify the bug in this C# method intended to find the intersection point of two linked lists: public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { ListNode a = headA, b = headB; while (a != b) { a = a.next; b = b.next; if (a == null && b == null) return null; } return a; }

medium

A. It uses incorrect comparison operator for nodes

B. It returns null too early when both pointers are null

C. It does not switch pointers to the other list when reaching null

D. It does not handle empty lists

Solution

1. Step 1: Analyze pointer movement in the loop

   Both pointers move forward but never switch to the other list head when reaching null, so they may never meet.

2. Step 2: Understand the consequence

   Without switching, if lists differ in length, pointers become null at different times and miss intersection.

3. Final Answer:

   It does not switch pointers to the other list when reaching null -> Option C

4. Quick Check:

   Switch pointers at null to find intersection [OK]

Hint: Switch pointers to other list head when null to align traversal [OK]

Common Mistakes:

• Not switching pointers causes infinite loop or wrong result
• Returning null too early without full traversal
• Confusing node equality with value equality

5. Given two singly linked lists that may or may not intersect, which approach correctly finds the intersection node in O(m+n) time and O(1) space? Options: A) Use two pointers starting at heads; when a pointer reaches end, switch it to the other list's head; continue until they meet. B) Use a hash set to store nodes of first list, then check nodes of second list for presence. C) Calculate lengths of both lists, advance longer list pointer by difference, then move both pointers until node.val match. D) Reverse both lists and compare nodes from start until mismatch. Which is the best approach for this problem?

hard

A. Two pointers switching heads when reaching end

B. Hash set to store nodes of first list

C. Advance longer list pointer by length difference then compare node.val

D. Reverse both lists and compare nodes

Solution

1. Step 1: Evaluate time and space complexity of each approach

   Two pointers switching heads when reaching end uses two pointers switching heads, runs in O(m+n) time and O(1) space.

2. Step 2: Compare with other options

   Hash set to store nodes of first list uses extra space O(m); Advance longer list pointer by length difference then compare node.val is incorrect because it compares values instead of node references; Reverse both lists and compare nodes is destructive and inefficient.

3. Step 3: Choose the best approach

   Two pointers switching heads when reaching end is clean, efficient, and uses constant space without modifying lists.

4. Final Answer:

   Two pointers switching heads when reaching end -> Option A

5. Quick Check:

   Two-pointer switch method = A [OK]

Hint: Use two pointers switching heads for O(1) space and linear time [OK]

Common Mistakes:

• Using extra space unnecessarily
• Modifying lists by reversing
• Comparing node values instead of references