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.