Intersection Point of Two Linked Lists in DSA C

Mental Model

Two linked lists may share some nodes at the end. The intersection point is the first shared node. We find it by aligning the lists and moving together.

Analogy: Imagine two roads merging into one. Before merging, they are separate paths. The intersection point is where they join and share the same path forward.

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

Dry Run Walkthrough

Input: List A: 1->2->3->4->5, List B: 9->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: lenA=5, lenB=3

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

Why: Knowing lengths helps align both lists to same remaining length.

Step 2: Advance headA by 2 nodes to align with headB

List A: 3 -> 4 -> 5 -> null
List B: 9 -> 4 -> 5 -> null

Why: Skip extra nodes in longer list so both have equal nodes left.

Step 3: Move both heads forward together until they meet

headA=3, headB=9 (not equal)
headA=4, headB=4 (equal)

Why: First common node is intersection point.

Result:

4 -> 5 -> null is the intersection starting at node with value 4

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Get length of linked list
int getLength(Node* head) {
    int length = 0;
    while (head) {
        length++;
        head = head->next;
    }
    return length;
}

// Find intersection point
Node* getIntersectionNode(Node* headA, Node* headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);

    // Align heads
    while (lenA > lenB) {
        headA = headA->next; // advance longer list
        lenA--;
    }
    while (lenB > lenA) {
        headB = headB->next; // advance longer list
        lenB--;
    }

    // Move together
    while (headA && headB) {
        if (headA == headB) {
            return headA; // intersection found
        }
        headA = headA->next;
        headB = headB->next;
    }
    return NULL; // no intersection
}

// Print list from given node
void printList(Node* head) {
    while (head) {
        printf("%d", head->data);
        if (head->next) printf(" -> ");
        head = head->next;
    }
    printf(" -> null\n");
}

int main() {
    // Create shared nodes
    Node* node4 = newNode(4);
    node4->next = newNode(5);

    // List A: 1->2->3->4->5
    Node* headA = newNode(1);
    headA->next = newNode(2);
    headA->next->next = newNode(3);
    headA->next->next->next = node4;

    // List B: 9->4->5
    Node* headB = newNode(9);
    headB->next = node4;

    Node* intersection = getIntersectionNode(headA, headB);
    if (intersection) {
        printf("Intersection at node with value: %d\n", intersection->data);
        printf("Intersection list: ");
        printList(intersection);
    } else {
        printf("No intersection found\n");
    }
    return 0;
}

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

Calculate lengths of both lists to know difference

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

Advance longer list head to align both lists

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

Advance longer list head to align both lists

while (headA && headB) { if (headA == headB) return headA; headA = headA->next; headB = headB->next; }

Move both pointers together until intersection or end

Output

Intersection at node with value: 4

Intersection list: 4 -> 5 -> null

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 other (O(m*n)), this method is efficient by aligning lengths first

Edge Cases

No intersection (two separate lists)

Function returns NULL and prints 'No intersection found'

DSA C

return NULL; // no intersection

One or both lists empty

Function returns NULL immediately as no nodes to compare

DSA C

while (headA && headB) { ... }

Intersection at head (both lists start at same node)

Function returns head immediately as intersection

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 pattern by aligning lengths and moving pointers together.

Common Mistakes

Mistake: Comparing node values instead of node addresses for intersection
Fix: Compare node pointers (addresses) to find actual shared nodes, not just values

Summary

Finds the first shared node where two linked lists intersect.

Use when two lists may merge and you want to find the merge point.

Align lists by length difference, then move pointers together to find intersection.