380. Intersection of Two Linked

Description

Write a program to find the node at which the intersection of two singly linked lists begins.

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.

Example

Example 1:

Input:

A:          a1 → a2

                  ↘

                    c1 → c2 → c3

                  ↗           

B:    b1 → b2 → b3

Output: c1

Explanation ：begin to intersect at node c1.

Example 2:

Input:

Intersected at 6

1->2->3->4->5->6->7->8->9->10->11->12->13->null

6->7->8->9->10->11->12->13->null

Output: Intersected at 6

Explanation：begin to intersect at node 6.

Challenge

Your code should preferably run in O(n) time and use only O(1) memory.

思路：

这个题最直接的思路是用哈希表存储一个一个链表的遍历结果，然后依次查找另一个链表的node在不在其中，但是这不符合题目要求。

第二个思路是，因为两个链表的长度不确定，如果是长度一样的链表就会容易比较，因为可以并行比较，那么为了进行并行比较就可以先得到链表长度，然后将两个链表遍历到两者长度一样，再开始比较。

第三个思路参考环状链表，将链表1的尾巴和链表2的头连起来， 如果两者有共同节点那么必然有环存在，首先用快慢指针遍历链表，当两个指针重合时代表存在环，然后将慢指针重新回到链表头，与快指针同时一步一步的往前走，两者相遇的地方即为相交点（这个结论据说已经被证明）。(类似的题有 102. Linked List Cycle：https://www.lintcode.com/problem/linked-list-cycle/description 103. Linked List Cycle IIFollow： https://www.lintcode.com/problem/linked-list-cycle-ii/description）

Description

Leaderboard

Note

Discuss

Solution

My Submissions

Open IDE

代码：

第二种思路

第三种思路