Leetcode-Java: Intersection of Two Linked Lists

Leetcode-Java: Intersection of Two Linked Lists

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.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Naive Way: 对每一A node, 遍历一遍B node,看是否交汇。这样的算法复杂度是O(n^2)。
但是题目要求了O(n) ，说明就一定存在O(n)的解法。链表有一个重要的特性就是有指针。
这些指针可以被灵活使用，这里让我想起了Populating Next Right Pointers in Each Node II里那个把next指针指向父节点的人，当时这个做法一下子直接打破了常规的想法，让指针不再局限于它的名字，我们其实也可以将left 和 right指向父节点什么的，这种约定俗成的变量名造成了先入为主的思维，往往会限制我们的想法。

那么看来要实现O(n)就必须利用好这些指针了，但是这道题不同于树，每一个节点只有一个指针，如果我们改变某一个指针，就断掉了，就无法修复了。所以我们不能断掉这些指针，但仍可以在不断掉整个链的情况下改变这些指针。

一开始我的想法是交叉A 链表和B链表的指针，看能不能弄出些名堂，但是无论怎么交叉，都只是将A和B前面的部分增长变短，问题就变成了对一个长度不同的A,B链表求交汇点。所以这样的尝试是失败的。

其实有一个节点的指针是一直没有用的，就是最后一个节点的指针，连接它到任意一个位置都改变了整个链表的结构，没错，增加了一个圈。这时才发现题目中的Notes是在给提示，前面有做过用龟兔赛跑的办法求圈的起始位置的题目，这里就可以用上了。当把尾部节点的指针链接至任意一个链表的开头，就变成一个含圈链表求圈起始位置的题目。而龟兔赛跑的算法复杂度正好是O(n)。具体龟兔赛跑是怎么回事，这里有一个比较好的教程Detecting a Loop in Singly Linked List - Tortoise & Hare

Read full article from Leetcode-Java: Intersection of Two Linked Lists