《剑指offer》刷题笔记（分解让复杂问题简单）：复杂链表的复制

野性酷女 2022-06-06 11:55 123阅读 0赞

# 《剑指offer》刷题笔记（分解让复杂问题简单）：复杂链表的复制 #

--------------------

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **代码地址：[https://github.com/WordZzzz/Note/tree/master/AtOffer][https_github.com_WordZzzz_Note_tree_master_AtOffer]**
 *  **刷题平台：[https://www.nowcoder.com/][https_www.nowcoder.com]**
 *  **题  库：剑指offer**
 *  **编  者：WordZzzz**

--------------------

*  剑指offer刷题笔记分解让复杂问题简单复杂链表的复制
    
     *  前言
     *  题目描述
     *  解题思路
     *  C版代码实现
     *  Python版代码实现

## 前言 ##

在计算机领域有一类算法叫分治法，即“分而治之”。采用的就是各个击破的思想，我们把分解后的小问题各个解决，然后把小问题的解决方案结合起来解决大问题。

## 题目描述 ##

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

## 解题思路 ##

我们可以将复杂链表的复制过程分解为三个步骤。在写代码的时候我们每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明了了。

大部分人首先想到的可能是先复制复杂指针的label和next，然后再查找random并更新。查找random又分为两种，一种是每次都从头查找，时间复杂度为O(n^2)；另一种是空间换时间，复制label和next的同时建立一个hash表来存放新旧复杂指针的对应关系，所以后续只需一步就能找到random，算法时间复杂度为O(n)。

我们这里采用三步走战略，也是剑指offer上推崇的方法：

*  第一步：复制复杂指针的label和next。但是这次我们把复制的结点跟在元结点后面，而不是直接创建新的链表；
 *  第二步：设置复制出来的结点的random。因为新旧结点是前后对应关系，所以也是一步就能找到random；
 *  第三步：拆分链表。奇数是原链表，偶数是复制的链表。

有图思路更清晰：

![SouthEast][]

![SouthEast 1][]

![SouthEast 2][]

## C++版代码实现 ##

/*
    /*
    struct RandomListNode {
        int label;
        struct RandomListNode *next, *random;
        RandomListNode(int x) :
                label(x), next(NULL), random(NULL) {
        }
    };
    */
    class Solution {
    public:
        //第一步，复制复杂指针的label和next
        void CloneNodes(RandomListNode* pHead){
            RandomListNode* pNode = pHead;
            while(pNode != NULL){
                RandomListNode* pCloned = new RandomListNode(0);
                pCloned->label = pNode->label;
                pCloned->next = pNode->next;
                pCloned->random = NULL;
    
                pNode->next = pCloned;
                pNode = pCloned->next;
            }
        }
        //第二步，处理复杂指针的random
        void ConnectSiblingNodes(RandomListNode* pHead){
            RandomListNode* pNode = pHead;
            while(pNode != NULL){
                RandomListNode* pCloned = pNode->next;
                if(pNode->random != NULL)
                    pCloned->random = pNode->random->next;
                pNode = pCloned->next;
            }
        }
        //第三步，拆分复杂指针
        RandomListNode* ReconnectNodes(RandomListNode* pHead){
            RandomListNode* pNode = pHead;
            RandomListNode* pCloneHead = NULL;
            RandomListNode* pCloneNode = NULL;
            if(pNode != NULL){
                pCloneHead = pCloneNode = pNode->next;
                pNode->next = pCloneNode->next;
                pNode = pNode->next;
            }
            while(pNode != NULL){
                pCloneNode->next = pNode->next;
                pCloneNode = pCloneNode->next;
                pNode->next = pCloneNode->next;
                pNode = pNode->next;
            }
            return pCloneHead;
        }
    
        RandomListNode* Clone(RandomListNode* pHead)
        {
            CloneNodes(pHead);
            ConnectSiblingNodes(pHead);
            return ReconnectNodes(pHead);
        }
    };

## Python版代码实现 ##

# -*- coding:utf-8 -*-
    # class RandomListNode:
    #     def __init__(self, x):
    #         self.label = x
    #         self.next = None
    #         self.random = None
    class Solution:
        #RandomListNode
        def CloneNodes(self, pHead):
            pNode = pHead
            while pNode is not None:
                pCloned = RandomListNode(0)
                pCloned.label = pNode.label
                pCloned.next = pNode.next
                pCloned.random = None
    
                pNode.next = pCloned
                pNode = pCloned.next
    
        def ConnectSiblingNodes(self, pHead):
            pNode = pHead
            while pNode is not None:
                pCloned = pNode.next
                if pNode.random is not None:
                    pCloned.random = pNode.random.next
                pNode = pCloned.next
    
        def ReconnectNodes(self, pHead):
            pNode = pHead
            pCloneHead = None
            if pNode is not None:
                pCloneHead = pCloneNode = pNode.next
                pNode.next = pCloneNode.next
                pNode = pNode.next
            while pNode is not None:
                pCloneNode.next = pNode.next
                pCloneNode = pCloneNode.next
                pNode.next = pCloneNode.next
                pNode = pNode.next
            return pCloneHead
    
        def Clone(self, pHead):
            # write code here
            self.CloneNodes(pHead)
            self.ConnectSiblingNodes(pHead)
            return self.ReconnectNodes(pHead)

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_github.com_WordZzzz_Note_tree_master_AtOffer]: https://github.com/WordZzzz/Note/tree/master/AtOffer
[https_www.nowcoder.com]: https://www.nowcoder.com/
[SouthEast]: /images/20220606/06975ce26dfc4b228fed4fcfded4a284.png
[SouthEast 1]: /images/20220606/b36f72a066f44148b3b0befbe66f89d4.png
[SouthEast 2]: /images/20220606/0d06a7c0ca80425c9212cd122c1e2d90.png