导航
导航
文章目录
  1. 题目
  2. 翻译
  3. 延伸

LeetCode-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.

翻译

编写程序,找到两个单链表的交叉起点。
例如,下面两个链表:
A:     a1 → a2
           ↘
             c1 → c2 → c3
           ↗
B:   b1 → b2 → b3
从c1节点开始交叉。
注意:
如果两个链表无交叉,返回null。
函数返回后链表必须保持它们起始的结构。
你可以认为在整个链表结构中没有循环。
你的代码应该在O(n)时间,并只使用O(1)的内存。

经典问题,分析可知如果两个链表有交叉,那么从交叉起点开始,两个链表后面的元素完全一样。
设立两个指针,首先遍历得到两个链表的长度,设长度相差n,将长的链表先走n步,然后两个链表一起遍历,如果遇到公共节点则返回,如果到尾部则无交叉,返回null:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null)
return null;

int lenA = 0, lenB = 0;
ListNode tmpA = headA, tmpB = headB;
while (tmpA != null) {
lenA++;
tmpA = tmpA.next;
}
while (tmpB != null) {
lenB++;
tmpB = tmpB.next;
}
tmpA = headA;
tmpB = headB;
while (lenA > lenB) {
tmpA = tmpA.next;
lenA--;
}
while (lenB > lenA) {
tmpB = tmpB.next;
lenB--;
}
while (tmpA != null) {
if (tmpA == tmpB)
return tmpA;
tmpA = tmpA.next;
tmpB = tmpB.next;
}

return null;
}
}

延伸

1、判断两个链表是否相交:判断尾节点是否相等即可;
2、如果有环:
(1) 一个有环一个无环,无交点;
(2)都无环,参考本题及1;
(3)都有环,判断一个头结点是否在另一个的环上。

参考;
http://www.cnblogs.com/felixfang/p/3821923.html