1. 题目描述

输入两个链表,找出它们的第一个公共结点。

2. 思路分析

2.1 思路一:栈实现

在第一个公共节点前的节点都是不相同的,因此只要倒序遍历两个链表,找出最后一个出现的相同节点即可。

因为链表不能倒序遍历,所以借助栈实现。

2.2 思路二:快慢指针

假设链表 A 长度大于链表 B 长度,它们的长度差为 diff。

让 A 的指针先移动 diff 的位移,然后 A 和 B 的指针再同时向后移动,每次比较节点,选出第一个出现的相同节点。

3. 代码实现

为了方便,先简单实现节点数据结构:

1
2
3
4
5
6
class Node {
constructor(value, next) {
this.value = value
this.next = next
}
}

3.1 思路一:栈实现

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
/**
* 思路一:利用栈实现
*
* @param {Node} list1
* @param {Node} list2
*/
function method1(list1, list2) {
const stack1 = [],
stack2 = []

let node = list1
while (node) {
stack1.push(node)
node = node.next
}

node = list2
while (node) {
stack2.push(node)
node = node.next
}

node = null
while (stack1.length && stack2.length) {
let top1 = stack1.pop(),
top2 = stack2.pop()
if (top1 === top2) {
node = top1
} else {
break
}
}

return node
}

3.2 思路二:快慢指针

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
47
48
/**
* 思路二:快慢指针
*
* @param {Node} list1
* @param {Node} list2
*/
function method2(list1, list2) {
let length1 = 0,
length2 = 0

let node = list1
while (node) {
++length1
node = node.next
}

node = list2
while (node) {
++length2
node = node.next
}

let diff = Math.abs(length1 - length2),
longList = null,
shortList = null
if (length1 > length2) {
longList = list1
shortList = list2
} else {
longList = list2
shortList = list1
}

while (diff > 0) {
longList = longList.next
--diff
}

while (longList && shortList) {
if (longList === shortList) {
return longList
}
longList = longList.next
shortList = shortList.next
}

return null
}

3.3 测试代码

1
2
3
4
5
6
const node4th = new Node(4)
const node3th = new Node(3, node4th)
const list1 = new Node(1, new Node(2, new Node(3, node3th)))
const list2 = new Node(5, new Node(6, node3th))

console.log(method2(list1, list2))