How to Solve Intersection of Linked List

Written By
Adam Bhula

Intersection of Linked List Introduction

The Intersection of linked list problem (also known as the Intersection of two linked list problem) asks us to return the node at which two linked lists intersect, if none then we return None. This problem requires us to consider the lengths of the given linked lists before using our pointers. Using the lengths we can adjust our starting positions accordingly. By using these two pointers effectively to traverse the lists we can find the point in which they intersect without comparing every node.

Intersection of Linked List Problem

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return none.

Intersection of Linked List Solutions

We can solve this problem using two-pointers. We start by finding the lengths of the two linked lists and adjust the starting positions of the pointers accordingly. This step ensures that both pointers are at the same relative position from the end of their respective lists. Next, we traverse the linked lists simultaneously using the two pointers. We keep moving the pointers one node at a time until either they meet at an intersection point or both reach the end of their lists. By doing this, we can search for the intersection point without having to compare every node.

If the pointers meet, it means we have found the intersection point. We can return that node as the result. If the pointers reach the end of their lists without meeting, it let's us know that there is no intersection between the two linked lists. In this case, we return 'None' to signify the absence of an intersection.

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

def getIntersectionNode(headA, headB):
    # Check if either list is empty
    if not headA or not headB:
        return None

    # Get the lengths of both lists
    lenA, lenB = 0, 0
    nodeA, nodeB = headA, headB
    while nodeA:
        lenA += 1
        nodeA = nodeA.next
    while nodeB:
        lenB += 1
        nodeB = nodeB.next

    # Move the longer list's head pointer to align the lengths
    while lenA > lenB:
        headA = headA.next
        lenA -= 1
    while lenB > lenA:
        headB = headB.next
        lenB -= 1

    # Traverse both lists to find the intersection point
    while headA != headB:
        headA = headA.next
        headB = headB.next

    # Return the intersection node (or None if no intersection)
    return headA

# Create linked lists for testing
# Intersection point at node with value 8
common = ListNode(8, ListNode(4, ListNode(5)))
headA = ListNode(4, ListNode(1, common))
headB = ListNode(5, ListNode(6, ListNode(1, common)))

# Test our solution
intersection = getIntersectionNode(headA, headB)
if intersection:
    print("Intersection at node with value:", intersection.val)
    print("No intersection")

#Expected output: 8

Time/Space Complexity Analysis

  • Time Complexity: O(m + n), where m and n are the lengths of the two linked lists. We need to traverse both lists to calculate their lengths and then traverse them again simultaneously until we find the intersection point or reach the end. This means that the time complexity is linear with respect to the lengths of the lists.
  • Space Complexity: O(1), as we only use a constant amount of extra space to store the two pointers and a few other variables.

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.