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))