Intersection of Two Linked Lists

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

Example

The following two linked lists:

begin to intersect at node c1.

Note

  • 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.
Challenge

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

思路:

  1. 二个链表有交叉,那么这2个链表的后一段元素必然是公共的。
  2. 算出2个链表的长度,长链表中一定有某一个位置使得和短链表的长度相等。
  3. 从该位置同时向后查找,如果发现相同的元素,这个点就是交叉的起点

 

发表评论