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:

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或者相遇

代码