Получите точку пересечения двух связанных списков, подсчитав узлы

В системе есть два односвязных списка. Из-за какой-то ошибки программирования конечный узел одного из связанных списков был связан со вторым списком, образуя перевернутый Y-образный список. Напишите программу для получения точки слияния двух связанных списков.

На приведенной выше диаграмме показан пример с двумя связанными списками, имеющими 15 в качестве точки пересечения.

Подход: можно заметить, что количество узлов при обходе первого связанного списка, а затем от заголовка второго связанного списка до точки пересечения равно количеству узлов, участвующих в обходе второго связанного списка, а затем от заголовка списка. первый список до точки пересечения. Учитывая приведенный выше пример, начните обход двух связанных списков с двумя указателями curr1 и curr2 , указывающими на заголовки данных связанных списков соответственно.

1. Если curr1 != null, обновите его, чтобы он указывал на следующий узел, в противном случае он обновляется, чтобы указывать на первый узел второго списка.
2. Если curr2 != null , тогда обновите его, чтобы он указывал на следующий узел, в противном случае он обновляется, чтобы указывать на первый узел первого списка.
3. Повторяйте вышеуказанные шаги, пока curr1 не равен curr2 .

Два указателя curr1 и curr2 теперь будут указывать на один и тот же узел, то есть на точку слияния.
Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N + M).
Вспомогательное пространство : O(1).