Chipmunk & Panda

-- 鼠熊部落格

All work and no play makes Jack a dull boy.

复杂链表的复制

  数据结构与算法    

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

初见

额外维护两个列表，记录已经复制过的节点以及对应原节点，然后对每个节点执行：

  1. 如果这个节点已经被复制过（也就是被访问过），则直接从已复制节点列表中取出该复制节点，否则进行复制，并分别将原节点和复制节点放入已访问列表和已复制列表中；
  2. 对该节点的 next 节点重复上述操作，然后把复制的 next 链接上；
  3. 对该节点的 random 节点重复上述操作，然后把复制的 random 链接上。
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
49
50
51
52
53
54
55
56
57
58
59
60
/*
function Node(val, next, random) {
    this.val = val;
    this.next = next;
    this.random = random;
};
*/

var copyRandomList = function (head) {
  if (!head) {
    return null
  }

  let node = head
  let nodeVisitList = []
  let nodeCpyList = []
  let nodeCpy = null
  let nodeNextCpy = null
  let nodeRandomCpy = null
  let index = null

  while (node) {
    index = nodeVisitList.indexOf(node)
    if (index >= 0) {
      nodeCpy = nodeCpyList[index]
    } else {
      nodeCpy = new Node(node.val, null, null)
      nodeVisitList.push(node)
      nodeCpyList.push(nodeCpy)
    }

    if (node.next) {
      index = nodeVisitList.indexOf(node.next)
      if (index >= 0) {
        nodeNextCpy = nodeCpyList[index]
      } else {
        nodeNextCpy = new Node(node.next.val, null, null)
        nodeVisitList.push(node.next)
        nodeCpyList.push(nodeNextCpy)
      }
      nodeCpy.next = nodeNextCpy
    }

    if (node.random) {
      index = nodeVisitList.indexOf(node.random)
      if (index >= 0) {
        nodeRandomCpy = nodeCpyList[index]
      } else {
        nodeRandomCpy = new Node(node.random.val, null, null)
        nodeVisitList.push(node.random)
        nodeCpyList.push(nodeRandomCpy)
      }
      nodeCpy.random = nodeRandomCpy
    }

    node = node.next
  }

  return nodeCpyList[0]
}

JS 的 Map 类型可以接受 Object 作为 key，所以也可以把两个数组合并成一个 Map，不过除了代码简洁一些其他没啥区别。

改成递归要简洁很多：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var copyRandomList = function (head, nodeVisitList = [], nodeCpyList = []) {
  if (!head) {
    return null
  }

  let index = nodeVisitList.indexOf(head)
  if (index >= 0) {
    return nodeCpyList[index]
  }

  let nodeCpy = new Node(head.val, null, null)
  nodeVisitList.push(head)
  nodeCpyList.push(nodeCpy)
  nodeCpy.next = copyRandomList(head.next, nodeVisitList, nodeCpyList)
  nodeCpy.random = copyRandomList(head.random, nodeVisitList, nodeCpyList)

  return nodeCpy
}

链表拆分法

  1. 遍历链表，制作每个节点的拷贝（next、random 暂时不管），每个拷贝插入到对应原始节点后面（例如 A -> B -> C 变为 A -> A’ -> B -> B’ -> C -> C’）
  2. 遍历每一个原始节点，把 random 链接上（node.next.random = node.random.next）
  3. 遍历每一个原始节点，把 next 链接上（node.next.next = node.next.next.next），同时把原始链表的 next 复原。

这样就不用记录已复制过的节点，节省了空间，比较巧妙。

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
var copyRandomList = function (head) {
  if (!head) {
    return null
  }

  let node = head

  while (node) {
    node.next = new Node(node.val, node.next, null)

    node = node.next.next
  }

  let headCpy = head.next

  node = head
  while (node) {
    if (node.random) {
      node.next.random = node.random.next
    }

    node = node.next.next
  }

  while (head) {
    let nodeNext = head.next.next
    if (nodeNext) {
      head.next.next = nodeNext.next
    }
    head.next = nodeNext

    head = nodeNext
  }

  return headCpy
}