1. 题目描述

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

2. 思路分析

2.1 思路一:栈实现

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

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

2.2 思路二:快慢指针

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

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

3. 代码实现

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

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

3.1 思路一:栈实现

/**
 * 思路一:利用栈实现
 *
 * @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;
}
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

3.2 思路二:快慢指针

/**
 * 思路二:快慢指针
 *
 * @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;
}
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

3.3 测试代码

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));
1
2
3
4
5
6