Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

0%

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:

begin to intersect at node c1.

Example 1:

1
2
3
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

分析题解

一开始没什么头绪,感觉只能最原始的遍历,后来看了一些文章,发现比较简单的方式就是先找两个链表的长度差,因为从相交点开始肯定是长度一致的,这是个很好的解题突破口,找到长度差以后就是先跳过长链表的较长部分,然后开始同步遍历比较 A,B 链表;

代码

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// 算 A 的长度
int countA = 0;
ListNode tailA = headA;
while (tailA != null) {
tailA = tailA.next;
countA++;
}
// 算 B 的长度
int countB = 0;
ListNode tailB = headB;
while (tailB != null) {
tailB = tailB.next;
countB++;
}
tailA = headA;
tailB = headB;
// 依据长度差,先让长的链表 tail 指针往后移
if (countA > countB) {
while (countA > countB) {
tailA = tailA.next;
countA--;
}
} else if (countA < countB) {
while (countA < countB) {
tailB = tailB.next;
countB--;
}
}
// 然后同步遍历比较
while (tailA != null) {
if (tailA == tailB) {
return tailA;
} else {
tailA = tailA.next;
tailB = tailB.next;
}
}
return null;
}
请我喝杯咖啡