Задача:
Припустим существует два односвязных списка, которые пересекаются в некоторой точке и стают односвязным списком. Известно начало обох списков, но неизвестна точка пересечения. Также, не известны длины обеих списков и длины обох списков могут быть разными. Первый список может иметь n элементов, перед тем как он достигнет точки пересечения, а второй - m элементов, где m и n могут быть m = n, m < n, m > n. Реализовать алгоритм нахождения точки пересечения.
Представление односвязного списка
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
Решение:
Есть много способов реализации даной проблемы и мы рассмотрим только два.
1) Брутальный способ.
В этом способе мы сравниваем значения списков поэлементно, что дает нам сложность O(mn).
Вот пример на Java:
//Brute-Force solution
public static ListNode getIntersectionNodeBF(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode tmp = null;
while (headA != null) {
tmp = headB;
while (tmp != null) {
if (headA.val == tmp.val) {
return headA;
}
tmp = tmp.next;
}
headA = headA.next;
}
return null;
}
2) Главная идея второго способа состоит в том, что если данные два списка имеют точку пересечения, тогда она будет в конце этих списков, тоесть конецы списков будут одинаковые. Но у так как наши списки могут быть не одинаковой длинны мы должны уровнять их прежде чем мы начнем их сравнивать.
Алгоритм:
-
Найти длины (length1 and length2) данных списков.
-
Найти разницу diff между длинами.
-
Сделать diff шагов в большем списке
-
Пройти оба списка паралельно, пока не будет найден элемент пересечения.
Пример на Java:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
int length1 = 0, length2 = 0, diff = 0;
ListNode list1 = headA, list2 = headB;
while (list1 != null) {
length1++;
list1 = list1.next;
}
while (list2 != null) {
length2++;
list2 = list2.next;
}
list1 = headA;
list2 = headB;
diff = length1 - length2;
if (length2 > length1) {
list1 = headB;
list2 = headA;
diff = length2 - length1;
}
for (int i = 0; i < diff; i++) {
list1 = list1.next;
}
while (list1 != null && list2 != null) {
if (list1.val == list2.val) {
return list1;
}
list1 = list1.next;
list2 = list2.next;
}
return null;
}
}
