剑指 Offer 35. 复杂链表的复制

Posted on Edited on In , ,
转载自Leet Code《剑指Offer》

题目描述

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

示例：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]

输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]

输入：head = [] 输出：[]

提示：

  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。
  • 节点数目不超过 1000 。

我的思路

由于链表中的值不唯一、链表只能从前往后依次遍历，再加上random可能指向当前节点的前方/后方/null的特性， 考虑使用map和哈希表来实现。 思路是，考虑在常规链表复制 (一次遍历) 的基础上，如何复制random指针。

由于原始链表的每个节点和常规链表的每个节点都会对应新的数据域， 且链表复制的时候对于random部分，本质上是需要对链表内的各个节点之间的联系进行复制， 因此希望由i找到原始节点、由

在常规复制链表时，会对链表进行一次遍历。在遍历的同时：

  • 在map1内记录原始节点p对应的原始random节点；
  • 在map2内记录原始节点p对应的下标i；
  • 在哈希表map3记录下标i对应的原始节点p；
  • 在哈希表map4记录下标i对应的新节点p。

区分map3和map4的原因是链表节点指向的是数据域 (某个地址) 的特性。

当常规复制完成后，再回到新的链表头复制random部分。 对于第i个新节点p，由哈希表map3找到原链表中对应的第i个原始节点map3[i]，再通过map1找到其对应的原始random节点。 如果原始random节点不指向null的话，则先由map2找到原始random节点对应的下标i， 再由map4找到其对应的新的random节点map4[i]，就是新节点p的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
class MySolutionOffer35 {
	public Node copyRandomList(Node head) {
		
		int N = 1000;

		if (head==null) 
			return null;
		
	     Node newHead = null;
	     Node p = head; Node pre = newHead;
	     
	     HashMap<Node, Node> map1 = new HashMap();
	     HashMap<Node, Integer> map2 = new HashMap();
	     Node []map3 = new Node[N];
	     Node []map4 = new Node[N];
	     
	     int i = 0;
	     while (p!=null)
	     {
	    	 map1.put(p, p.random);
	    	 map2.put(p, i); 
	    	 map3[i] = p;
	    	 
	    	 if (newHead==null) 
	    	 {
	    		 newHead = new Node(p.val);
	    		 pre = newHead;
			 }
	    	 else
	    	 {
	    		 pre.next = new Node(p.val);
	    		 pre = pre.next;
	    	 }
	    	 map4[i] = pre;
	    	 
	    	 p = p.next; i+=1;
	     }
	     pre.next = null;
	     
	     p = newHead; 
	     i = 0;
	     
	     while (p!=null)
	     {
            Node randomNode = map1.get(map3[i]);
	    	if(randomNode==null)
	    		p.random = null;
	    	else 
	    	{
	    		int randomI = map2.get(randomNode);
	    		p.random = map4[randomI];
	    	}
	        p = p.next; 
	        i++;
	     }
	     
	     return newHead;
	}
}

方法一：回溯 + 哈希表

思路：利用回溯的方式，让每个节点的拷贝操作相互独立。

对于当前节点，首先对其进行拷贝， 然后进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝， 拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

具体地，用哈希表记录每一个节点对应新节点的创建情况。 遍历时，检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。 如果这两个节点中的任何一个节点的新节点没有被创建，都立刻递归地进行创建。 当拷贝完成，回溯到当前层时，即可完成当前节点的指针赋值。

注意一个节点可能被多个其他节点指向，因此可能递归地多次尝试拷贝某个节点。 为了防止重复拷贝，需要首先检查当前节点是否被拷贝过。 如果已经拷贝过，可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

在实际代码中，我们需要特别判断给定节点为空节点的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution1 {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}

时间复杂度: \(O(N)\). 对于每个节点，我们至多访问其「后继节点」和「随机指针指向的节点」各一次，均摊每个点至多被访问两次。

空间复杂度: \(O(N)\). 哈希表的空间开销。

方法二：迭代 + 节点拆分

思路：希望省去方法一当中哈希表所消耗的空间。

首先，将该链表中每一个节点拆分为两个相连的节点。 例如，对于链表\(A→B→C\)， 我们可以将其拆分为\(A→A'→B→B'→C→C'\)。 即，对于任意一个原节点\(S\)，其拷贝节点 \(S'\) 即为其后继节点。

这样，我们可以直接找到每一个拷贝节点 \(S'\) 的随机指针应当指向的节点， 即为其原节点 \(S\) 的随机指针指向的节点 \(T\) 的后继节点 \(T'\) 。

需要注意原节点的随机指针可能为空。

当完成了拷贝节点 \(S'\) 的随机指针 \(T'\) 的赋值， 就只需要将这个链表按照原节点 \(S\) 与拷贝节点 \(S'\) 的种类进行拆分即可，只需要遍历一次。

同样需要注意最后一个拷贝节点的后继节点为空的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution2 {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        Node headNew = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        return headNew;
    }
}

时间复杂度：\(O(N)\). 只需要遍历三次。(如果在计算拷贝节点的随机指针的同时计算其后继指针，则只需要遍历两次。)

空间复杂度：\(O(1)\). 注意返回值不计入空间复杂度的计算。