Intersection of Linked List

How to Solve Intersection of Linked List

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 lets 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)
else:
    print("No intersection")

#Expected output: 8

Time/Space Complexity Analysis