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. 這道題確實(shí)做過，印象深刻。通過做輔助線，把問題轉(zhuǎn)換成熟悉的問題，再用熟悉的配方來解決。假設(shè)有兩條鏈表A,B，我們先遍歷A到A的結(jié)尾然后把A的尾巴指向A的頭部，這樣一來，就有一個cycle，如果我們再從B開始用快慢指針大法去檢測這個cycle，并找到cycle所在的地方，就是兩條鏈表的intersection 開始的地方。如果AB沒有intersection,那么我們遍歷B就不會遇到cycle。