Leetcode 160. 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:

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.

s思路： 1. 这道题确实做过，印象深刻。通过做辅助线，把问题转换成熟悉的问题，再用熟悉的配方来解决。假设有两条链表A,B，我们先遍历A到A的结尾然后把A的尾巴指向A的头部，这样一来，就有一个cycle，如果我们再从B开始用快慢指针大法去检测这个cycle，并找到cycle所在的地方，就是两条链表的intersection 开始的地方。如果AB没有intersection,那么我们遍历B就不会遇到cycle。