Write a program to find the
node at which the intersection of two singly linked lists begins.
For example, the following
two linked lists:
A: a1 → a2
↘
c1 → c2
→ c3
↗
B: b1
→ b2 → b3
begin to intersect at node c1.
Напишите функцию, которая ищет
вершину, с которой начинается пересечение двух односвязных списков. Например,
следующие списки
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1
→ b2 → b3
начинают пересекаться в
вершине c1.
// C++
/**
*
Definition for singly-linked list.
* struct
ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class
Solution {
public:
ListNode *getIntersectionNode(ListNode
*headA, ListNode *headB) {
}
};
// Java
/**
*
Definition for singly-linked list.
* public
class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class
Solution {
public ListNode getIntersectionNode(ListNode headA,
ListNode headB) {
}
}
структуры данных – связный список
Предположим, что входные
списки имеют одинаковую длину. Тогда установим на головы каждого из них по
указателю. Двигаем последовательно оба указателя на одну позицию вправо, пока
они не будут указывать на одну и ту же ячейку памяти.
Однако в нашем случае длины
списков могут быть разные. Пусть lenA
и lenB – длины списков (их можно
вычислить за O(n)). Установим два
указателя на головы списков. Указатель, установленный на голову более длинного
списка, продвинем на | lenA – lenB | позиций вперед. Далее действуем
как будто бы списки имеют одинаковую длину.
Реализация алгоритма
class Solution
{
public:
ListNode
*getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode *a =
headA, *b = headB;
int lenA = 0, lenB = 0;
while(a != NULL)
{
lenA++;
a = a->next;
}
while(b != NULL)
{
lenB++;
b = b->next;
}
a = headA; b =
headB;
if (lenA > lenB)
{
for(int i = 0; i <
lenA - lenB; i++)
a = a->next;
}
else
{
for(int i = 0; i <
lenB - lenA; i++)
b = b->next;
}
while(a != b)
{
a = a -> next;
b = b -> next;
}
return a;
}
};
Java реализация
class Solution
{
public ListNode getIntersectionNode(ListNode headA,
ListNode headB)
{
ListNode a = headA,
b = headB;
int lenA = 0, lenB = 0;
while(a != null)
{
lenA++;
a = a.next;
}
while(b != null)
{
lenB++;
b = b.next;
}
a = headA; b =
headB;
if (lenA > lenB)
{
for(int i = 0; i <
lenA - lenB; i++)
a = a.next;
}
else
{
for(int i = 0; i <
lenB - lenA; i++)
b = b.next;
}
while(a != b)
{
a = a.next;
b = b.next;
}
return a;
}
}