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

Intersection Point of Two Linked Lists

📖 Scenario: Imagine two train tracks that merge at some point and continue as one track. We want to find the exact point where these two tracks join. In programming, this is like finding the intersection point of two linked lists.

🎯 Goal: You will build two linked lists that share some nodes at the end. Then, you will write code to find the node where they intersect.

📋 What You'll Learn

Create two linked lists with some shared nodes

Use a helper variable to store the length of each list

Implement logic to find the intersection node

Print the value of the intersection node or None if no intersection

💡 Why This Matters

🌍 Real World

Finding intersection points is useful in network routing, version control systems, and merging data streams.

💼 Career

Understanding linked list intersections helps in technical interviews and solving problems related to memory and data structure optimization.

1

Create two linked lists with shared nodes

Create a class called Node with attributes val and next. Then create these nodes exactly: shared1 = Node(8), shared2 = Node(10), link shared1.next = shared2. Create first list nodes headA = Node(3), nodeA2 = Node(7), link headA.next = nodeA2, nodeA2.next = shared1. Create second list nodes headB = Node(99), nodeB2 = Node(1), link headB.next = nodeB2, nodeB2.next = shared1.

DSA Python

# Define Node class and create linked lists with shared nodes
# Your code here

Hint

Start by defining the Node class with val and next. Then create nodes and link them as described.

2

Calculate lengths of both linked lists

Create a function called get_length that takes a head node and returns the length of the linked list. Then create two variables lenA and lenB by calling get_length(headA) and get_length(headB) respectively.

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

shared1 = Node(8)
shared2 = Node(10)
shared1.next = shared2

headA = Node(3)
nodeA2 = Node(7)
headA.next = nodeA2
nodeA2.next = shared1

headB = Node(99)
nodeB2 = Node(1)
headB.next = nodeB2
nodeB2.next = shared1

# Define get_length function and calculate lenA and lenB
# Your code here

Hint

Use a while loop to count nodes until you reach the end (None).

3

Find the intersection node

Create a function called get_intersection_node that takes headA, headB, lenA, and lenB. Inside, move the longer list's head forward by the difference in lengths. Then move both heads forward together until they meet or reach None. Return the intersection node or None. Call this function with headA, headB, lenA, and lenB and store the result in intersection.

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

shared1 = Node(8)
shared2 = Node(10)
shared1.next = shared2

headA = Node(3)
nodeA2 = Node(7)
headA.next = nodeA2
nodeA2.next = shared1

headB = Node(99)
nodeB2 = Node(1)
headB.next = nodeB2
nodeB2.next = shared1

def get_length(head):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    return length

lenA = get_length(headA)
lenB = get_length(headB)

# Define get_intersection_node function and find intersection
# Your code here

Hint

Move the longer list's pointer forward by the difference in lengths, then move both pointers together until they meet.

4

Print the intersection node value

Print the value of the intersection node if it exists, otherwise print None.

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

shared1 = Node(8)
shared2 = Node(10)
shared1.next = shared2

headA = Node(3)
nodeA2 = Node(7)
headA.next = nodeA2
nodeA2.next = shared1

headB = Node(99)
nodeB2 = Node(1)
headB.next = nodeB2
nodeB2.next = shared1

def get_length(head):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    return length

lenA = get_length(headA)
lenB = get_length(headB)

def get_intersection_node(headA, headB, lenA, lenB):
    currentA = headA
    currentB = headB
    if lenA > lenB:
        for _ in range(lenA - lenB):
            currentA = currentA.next
    else:
        for _ in range(lenB - lenA):
            currentB = currentB.next
    while currentA and currentB:
        if currentA == currentB:
            return currentA
        currentA = currentA.next
        currentB = currentB.next
    return None

intersection = get_intersection_node(headA, headB, lenA, lenB)

# Print the value of the intersection node or None
# Your code here

Hint

Check if intersection is not None, then print its val. Otherwise, print None.