Intersection of Two Linked Lists — LeetCode 160 Python Solution

The 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 null.

Example

Input

intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output

Intersected at '8'

Explanation

The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).

Python solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

Complexity

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 160. Intersection of Two Linked Lists is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems