Intersection of Two Linked Lists

Условие

Даны два однонаправленных связных списка headA и headB. Найдите узел, с которого начинается их пересечение. Если пересечения нет, верните null. Два списка могут пересекаться только в одном узле.

Примеры

Input: headA = [4, 1, 8, 4, 5], headB = [5, 6, 1, 8, 4, 5]

Output: Узел с value = 8

Explanation: Узлы 8, 4 и 5 находятся в обеих списках, начиная с узла 8.

Input: headA = [1, 9, 1, 2, 4], headB = [3, 2, 4]

Output: Узел с value = 2

Explanation: Узлы 2 и 4 находятся в обеих списках, начиная с узла 2.

Input: headA = [2, 6, 4], headB = [1, 5]

Output: null

Explanation: Эти два списка не пересекаются.

Решение

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
    var aPointer = headA
    var bPointer = headB
    
    // Если один из списков достигает конца, перескакиваем на другой список
    while (aPointer != bPointer) {
        aPointer = if (aPointer == null) headB else aPointer.next
        bPointer = if (bPointer == null) headA else bPointer.next
    }
    
    // Когда они совпадают, это точка пересечения (или null)
    return aPointer
}

Временная сложность

O(n + m), где n и m — длины списков headA и headB соответственно.

Пространственная сложность

O(1), так как мы используем только два указателя.