題目

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.

思路

先遍歷兩個鏈表求出各自的長度，分別用兩個指針指向其頭結點，長的那個鏈表節點先往后走兩者長度的差值個數節點，這樣可以保證當兩者相遇時肯定同時相遇，再同時往后遍歷，直到走到NULL或者相遇

代碼