LeetCode138_复制带随机指针的链表

2019-12-01

本篇博客主要参考了Reference1的内容，但是这篇博客里面没细讲random指针的复制，于是我又结合官方题解的方法三理解了一下给出了详细解析过程，最后用python语言解答LeetCode的138题

题目解析：

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或者空节点。

要求返回这个链表的深拷贝。
（必须返回给定头的拷贝作为克隆列表的引用）

深度拷贝为拷贝出的新对象在堆中重新分配一块内存区域。所以对新对象的操作不会影响原始对象

深拷贝也就是复制一份链表，这份新链表的所有结点都有自己独立的内存空间，比如新链表的1号结点指向新链表自己的3号结点，而不是原链表的3号结点

定义带随机指针的链表节点


    class Node:
        def __init__(self, val, next, random):
            self.val = val
            self.next = next
            self.random = random

我们可以看到，它的定义相比于普通链表的定义多了一个random随机指针。

解题思路：

需要返回链表的深拷贝，不能指向原链表的结点，那么是否有什么办法可以使新老两链表产生一定映射关系，建立联系，通过索引老结点来找到新结点。

这里介绍一种思路：

1.因为是单链表，除随机指针外只有next可以利用。
2.将旧链表中各个节点逐个拷贝后，将每个结点安插在旧结点的next结点。
3.旧链表指针只遍历旧链表，
4.新链表指针只遍历新结点，
5.然后将两个链表拆分，
6.返回新链表即可

这个思路第二步的意思是将新创建的结点先插在旧链表中间，最后逐个断开的意思。解释起来有点复杂，看下面的图就懂啦

因为要遍历链表所有结点，需要多次发生创建结点的行为，所以我们选择将它封装成一个函数,进行调用。


    def create_node(self, val):
        p = Node(val, None, None)
        return p

1.判断极端情况，如果链表为空，那么无法拷贝，或者说拷贝之后仍是一个空链表，直接返回NULL
2.创建新结点，逐个申请空间，赋值原链表中每个结点

avatar

3.通过更改指向，让新结点跟在老结点后面
（红箭头表示老结点向新结点的指向，蓝箭头表示新结点向老结点的指向）

avatar

4.补充random指针的复制

Case1.结点的random指针指的是链表内的某一结点（该结点非空，非自身）
Case2.结点的random指针指的是空指针
Case3.结点的random指针指的是自己（这个情况其实是Case1的一个特例，合并到Case1中处理）

avatar

5.拆分新老链表，使它们成为独立的两个链表，最终在没有改动老链表的前提下，返回新链表接口

avatar

至此，链表的深拷贝逻辑返回成功

代码实现：


    #coding:utf-8

    class Node:
        def __init__(self, val, next, random):
            self.val = val
            self.next = next
            self.random = random


    class Solution:
        def __init__(self):
            pass

        def create_node(self, val):
            p = Node(val, None, None)
            return p

        def copyRandomList(self, head: 'Node') -> 'Node':
            if head == None:
                return None

            cur, pre = head, None

            # 复制原链表，将新建的结点依次穿插在旧链表的结点之间
            while cur != None:
                pre = cur.next
                cur_copy = self.create_node(cur.val)
                cur_copy.next = pre
                cur.next = cur_copy
                cur = pre

            cur = head

            # # 处理random指针
            while cur:
                cur.next.random = cur.random.next if cur.random else None
                cur = cur.next.next

            # 断开新旧链表    
            cur = head
            head_copy = cur.next
            cur_copy = head_copy
            pre = cur_copy.next
            while pre != None:
                cur.next = pre
                cur_copy.next = pre.next
                cur_copy  = cur_copy.next
                cur = pre
                pre = cur_copy.next

            cur.next = None
            return head_copy

Reference：

1.【图文解析】复制带随机指针的链表（返回链表的深拷贝）
https://blog.csdn.net/qq_42351880/article/details/88984429

2.官方题解
https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/