Intersection Point of Two Linked Lists in DSA C - Build from Scratch

Intersection Point of Two Linked Lists

📖 Scenario: Imagine two train tracks that merge into one at some point. Each track is a linked list of stations. We want to find the station where the two tracks join.

🎯 Goal: Build a program to find the intersection point (node) of two singly linked lists if they merge. If they do not merge, the program should indicate no intersection.

📋 What You'll Learn

Create two linked lists with some nodes sharing the same tail nodes

Use pointers to traverse the linked lists

Implement logic to find the intersection node

Print the data value of the intersection node or indicate no intersection

💡 Why This Matters

🌍 Real World

Finding the intersection point of linked lists is useful in memory management, detecting shared resources, and debugging pointer-related issues in software.

💼 Career

Understanding linked list intersections helps in roles involving low-level programming, embedded systems, and software debugging where pointer manipulation is common.

1

Create two linked lists with shared nodes

Create a struct called Node with an int data and a Node* called next. Then create nodes to form two linked lists where the lists share the last three nodes. Use these exact nodes and values: 1 -> 2 -> 3 -> 4 -> 5 -> NULL for the first list and 9 -> 4 -> 5 -> NULL for the second list, where nodes with values 4 and 5 are shared.

DSA C

// Define struct Node and create nodes for two linked lists with shared tail nodes
// Your code here

Hint

Start by defining the Node structure. Then create the shared nodes first, so both lists can point to them.

2

Create helper function to get length of a linked list

Write a function called getLength that takes a Node* called head and returns the length of the linked list as an int. Use a while loop to count nodes until head is NULL.

DSA C

#include 
#include 

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

int main() {
    // Shared nodes
    Node* node4 = (Node*)malloc(sizeof(Node));
    node4->data = 4;
    Node* node5 = (Node*)malloc(sizeof(Node));
    node5->data = 5;
    node4->next = node5;
    node5->next = NULL;

    // First list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    Node* head1 = (Node*)malloc(sizeof(Node));
    head1->data = 1;
    Node* node2 = (Node*)malloc(sizeof(Node));
    node2->data = 2;
    Node* node3 = (Node*)malloc(sizeof(Node));
    node3->data = 3;
    head1->next = node2;
    node2->next = node3;
    node3->next = node4;

    // Second list: 9 -> 4 -> 5 -> NULL
    Node* head2 = (Node*)malloc(sizeof(Node));
    head2->data = 9;
    head2->next = node4;

    // Write the getLength function below
    // Your code here

    return 0;
}

Hint

Use a while loop to move through the list until head is NULL, counting nodes.

3

Implement function to find intersection node

Write a function called getIntersectionNode that takes two Node* parameters: head1 and head2. Use the getLength function to find lengths of both lists. Advance the longer list's pointer by the difference in lengths. Then move both pointers one step at a time until they point to the same node or reach NULL. Return the intersection Node* or NULL if no intersection.

DSA C

#include 
#include 

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

int getLength(Node* head) {
    int length = 0;
    while (head != NULL) {
        length++;
        head = head->next;
    }
    return length;
}

int main() {
    // Shared nodes
    Node* node4 = (Node*)malloc(sizeof(Node));
    node4->data = 4;
    Node* node5 = (Node*)malloc(sizeof(Node));
    node5->data = 5;
    node4->next = node5;
    node5->next = NULL;

    // First list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    Node* head1 = (Node*)malloc(sizeof(Node));
    head1->data = 1;
    Node* node2 = (Node*)malloc(sizeof(Node));
    node2->data = 2;
    Node* node3 = (Node*)malloc(sizeof(Node));
    node3->data = 3;
    head1->next = node2;
    node2->next = node3;
    node3->next = node4;

    // Second list: 9 -> 4 -> 5 -> NULL
    Node* head2 = (Node*)malloc(sizeof(Node));
    head2->data = 9;
    head2->next = node4;

    // Write the getIntersectionNode function below
    // Your code here

    return 0;
}

Hint

First, find the lengths of both lists. Then move the pointer of the longer list ahead by the difference. Finally, move both pointers step by step until they meet or reach the end.

4

Print the intersection node data or no intersection

In the main function, call getIntersectionNode with head1 and head2. If the returned pointer is not NULL, print "Intersection at node with data: %d\n" with the node's data. Otherwise, print "No intersection found\n".

DSA C

#include 
#include 

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

int getLength(Node* head) {
    int length = 0;
    while (head != NULL) {
        length++;
        head = head->next;
    }
    return length;
}

Node* getIntersectionNode(Node* head1, Node* head2) {
    int len1 = getLength(head1);
    int len2 = getLength(head2);

    while (len1 > len2) {
        head1 = head1->next;
        len1--;
    }
    while (len2 > len1) {
        head2 = head2->next;
        len2--;
    }

    while (head1 != NULL && head2 != NULL) {
        if (head1 == head2) {
            return head1;
        }
        head1 = head1->next;
        head2 = head2->next;
    }
    return NULL;
}

int main() {
    // Shared nodes
    Node* node4 = (Node*)malloc(sizeof(Node));
    node4->data = 4;
    Node* node5 = (Node*)malloc(sizeof(Node));
    node5->data = 5;
    node4->next = node5;
    node5->next = NULL;

    // First list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    Node* head1 = (Node*)malloc(sizeof(Node));
    head1->data = 1;
    Node* node2 = (Node*)malloc(sizeof(Node));
    node2->data = 2;
    Node* node3 = (Node*)malloc(sizeof(Node));
    node3->data = 3;
    head1->next = node2;
    node2->next = node3;
    node3->next = node4;

    // Second list: 9 -> 4 -> 5 -> NULL
    Node* head2 = (Node*)malloc(sizeof(Node));
    head2->data = 9;
    head2->next = node4;

    // Print the intersection node data or no intersection
    // Your code here

    return 0;
}

Hint

Call getIntersectionNode with head1 and head2. Check if the result is NULL. Print the node's data if found, else print no intersection.

Practice

1. What does the term intersection point of two linked lists mean?

easy

A. The node where both linked lists have the same value but different references

B. The node where both linked lists share the same reference

C. The first node of the longer linked list

D. The last node of the shorter linked list

Solution

1. Step 1: Understand linked list nodes and references

   Each node in a linked list has a reference (address) to the next node. Two lists intersect if they share the same node reference, not just the same value.

2. Step 2: Define intersection point

   The intersection point is the first node where both lists point to the exact same node object in memory.

3. Final Answer:

   The node where both linked lists share the same reference -> Option B

4. Quick Check:

   Intersection means shared node reference [OK]

Hint: Intersection means same node object, not just same value [OK]

Common Mistakes:

• Confusing same value with same node reference
• Thinking intersection is based on node values
• Assuming intersection is at list ends

2. Which of the following C code snippets correctly declares a node structure for a singly linked list used to find intersection?

easy

A. struct Node { int data; struct Node next; };

B. struct Node { int data; Node* next; };

C. typedef struct { int data; struct Node* next; } Node;

D. typedef struct Node { int data; struct Node* next; } Node;

Solution

1. Step 1: Understand correct struct declaration

   In C, to declare a linked list node, you define a struct with data and a pointer to the same struct type.

2. Step 2: Check each option

   typedef struct Node { int data; struct Node* next; } Node; correctly uses typedef and struct Node with a pointer to struct Node. struct Node { int data; Node* next; }; misses typedef and uses Node* without struct keyword. typedef struct { int data; struct Node* next; } Node; misses struct name. struct Node { int data; struct Node next; }; incorrectly uses struct Node next (not a pointer).

3. Final Answer:

   typedef struct Node { int data; struct Node* next; } Node; -> Option D

4. Quick Check:

   Correct struct with pointer to same struct [OK]

Hint: Use 'struct Node* next;' inside struct for pointer to next node [OK]

Common Mistakes:

• Forgetting 'struct' keyword before pointer type
• Using struct variable instead of pointer for next
• Missing typedef or struct name

3. Given the following code snippet to find the intersection point of two linked lists, what will be the output?

Node* getIntersectionNode(Node* headA, Node* headB) {
    Node *a = headA, *b = headB;
    while (a != b) {
        a = (a == NULL) ? headB : a->next;
        b = (b == NULL) ? headA : b->next;
    }
    return a;
}

// Lists:
// List A: 1 -> 2 -> 3 \
//                      6 -> 7 -> NULL
// List B:       4 -> 5 /

// Intersection at node with value 6
Node* result = getIntersectionNode(headA, headB);
printf("%d", result->data);

medium

A. 3

B. 5

C. 6

D. NULL

Solution

1. Step 1: Understand the two-pointer approach

   Two pointers traverse each list; when reaching end, switch to other list head. They meet at intersection or NULL if none.

2. Step 2: Trace pointers on given lists

   Lists intersect at node with value 6. Pointers will meet there after switching lists.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Two-pointer meet at intersection node value 6 [OK]

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

Common Mistakes:

• Assuming pointers meet at first node
• Not switching pointers to other list head
• Confusing node value with pointer address

4. Identify the bug in the following code snippet intended to find the intersection point of two linked lists:

Node* getIntersectionNode(Node* headA, Node* headB) {
    Node *a = headA, *b = headB;
    while (a != b) {
        if (a == NULL || b == NULL) {
            a = headB;
            b = headA;
        } else {
            a = a->next;
            b = b->next;
        }
    }
    return a;
}

medium

A. The loop may run infinitely if no intersection exists

B. Pointers should not switch lists when NULL

C. The function does not handle empty lists

D. The comparison should be 'a->data == b->data' instead of 'a != b'

Solution

1. Step 1: Analyze loop termination condition

   The loop ends when pointers a and b are equal (same node or NULL).

2. Step 2: Check pointer switching logic

   When a or b is NULL, they switch to other list head. But if no intersection, pointers cycle indefinitely without becoming equal.

3. Final Answer:

   The loop may run infinitely if no intersection exists -> Option A

4. Quick Check:

   Loop lacks proper NULL check, causing infinite loop [OK]

Hint: Add explicit NULL check to break loop if no intersection [OK]

Common Mistakes:

• Assuming pointers always meet
• Comparing node data instead of node pointers
• Not handling empty list inputs

5. You have two singly linked lists that may or may not intersect. Write a function to find the intersection point efficiently. Which approach below is best and why? A) Use two pointers starting at heads, switch to other list when reaching end, until they meet. B) Use nested loops to compare every node of list A with every node of list B. C) Store all nodes of list A in a hash set, then check nodes of list B for presence. D) Reverse both lists and compare nodes from the start until they differ.

hard

A. Two-pointer switching approach; O(n) time, O(1) space

B. Nested loops; O(n*m) time, O(1) space

C. Hash set approach; O(n+m) time, O(n) space

D. Reverse lists; modifies input and O(n) time

Solution

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

   Two-pointer switching approach; O(n) time, O(1) space uses two pointers switching lists, runs in linear time and constant space. Nested loops; O(n*m) time, O(1) space is nested loops, very slow. Hash set approach; O(n+m) time, O(n) space uses extra space for hash set. Reverse lists; modifies input and O(n) time modifies lists, which is not ideal.

2. Step 2: Choose best approach for efficiency and safety

   Two-pointer switching approach; O(n) time, O(1) space is best because it is efficient (O(n)) and does not use extra space or modify lists.

3. Final Answer:

   Two-pointer switching approach; O(n) time, O(1) space -> Option A

4. Quick Check:

   Two-pointer method is optimal for intersection detection [OK]

Hint: Two-pointer switch method is fastest and uses no extra space [OK]

Common Mistakes:

• Choosing nested loops causing slow performance
• Using extra memory unnecessarily
• Modifying input lists causing side effects