Intersection Point of Two Linked Lists in DSA C - Execution Trace

Concept Flow - Intersection Point of Two Linked Lists

Start at head of List1 and List2

↓

Calculate lengths of both lists

↓

Align start pointers by skipping extra nodes in longer list

↓

Traverse both lists together

↓

Check if nodes are same (by reference)

↓

Intersection

↓

End if no intersection

Find lengths, align starts, then move both pointers step-by-step to find the first common node.

Execution Sample

DSA C

Node* getIntersection(Node* head1, Node* head2) {
  int len1 = length(head1);
  int len2 = length(head2);
  while (len1 > len2) { head1 = head1->next; len1--; }
  while (len2 > len1) { head2 = head2->next; len2--; }
  while (head1 && head2) {
    if (head1 == head2) return head1;
    head1 = head1->next;
    head2 = head2->next;
  }
  return NULL;
}

This code finds the intersection node of two linked lists by aligning their starts and moving together.

Execution Table

Step	Operation	List1 Pointer	List2 Pointer	Action	Visual State
1	Calculate length of List1	head1 at Node A	head2 at Node X	Length1 = 5	List1: A->B->C->D->E->NULL List2: X->Y->C->D->E->NULL
2	Calculate length of List2	head1 at Node A	head2 at Node X	Length2 = 5	Same as above
3	Align pointers	head1 at Node A	head2 at Node X	Lengths equal, no skip	Pointers unchanged
4	Compare nodes	Node A	Node X	Not same, move both	Pointers move to B and Y
5	Compare nodes	Node B	Node Y	Not same, move both	Pointers move to C and C
6	Compare nodes	Node C	Node C	Same node found	Intersection at Node C
7	Return intersection	Node C	Node C	Return Node C	End

💡 Intersection found at Node C, pointers matched by reference.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
head1	Node A	Node A	Node B	Node C	Node C	Node C
head2	Node X	Node X	Node Y	Node C	Node C	Node C
len1	0	5	5	5	5	5
len2	0	5	5	5	5	5

Key Moments - 3 Insights

Why do we skip nodes in the longer list before comparing?

Because the lists may have different lengths, skipping extra nodes aligns the pointers so they have equal nodes left to traverse, ensuring correct comparison (see Step 3 in execution_table).

Why do we compare nodes by reference, not by value?

Intersection means the exact same node in memory, not just same value. So we check if pointers are equal (Step 6), not if data matches.

What if there is no intersection?

Both pointers will reach NULL without matching nodes, and the function returns NULL (not shown here but implied after Step 6).

Visual Quiz - 3 Questions

Look at the execution_table, what is the position of head1 after Step 4?

A Node B

B Node C

C Node A

D Node Y

💡 Hint

Check the 'List1 Pointer' column at Step 4 in execution_table.

At which step do head1 and head2 point to the same node?

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look for 'Same node found' in the Action column of execution_table.

If List1 was longer by 2 nodes, what would change in the execution_table?

A Steps 4 and 5 would be skipped

B Intersection would be found earlier

C Steps 3 would show skipping 2 nodes in List1

D Lengths would be equal

💡 Hint

Refer to Step 3 where pointer alignment happens by skipping extra nodes.

Concept Snapshot

Intersection Point of Two Linked Lists:
- Find lengths of both lists
- Skip extra nodes in longer list to align
- Move both pointers step-by-step
- Check if pointers are same (by reference)
- Return intersection node or NULL if none

Full Transcript

To find the intersection point of two linked lists, first calculate the lengths of both lists. Then, skip the extra nodes in the longer list so both pointers start equally far from the end. Next, move both pointers forward one node at a time, comparing if they point to the same node by reference. If yes, that node is the intersection. If no intersection exists, both pointers reach NULL and the function returns NULL.