剑指Offer（二十五）：复杂链表的复制

2017年12月13日11:16:03 8 7,353 °C
摘要

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

剑指Offer（二十五）：复杂链表的复制

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

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

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

我们这里采用三步：

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

有图思路更清晰：

剑指Offer（二十五）：复杂链表的复制

剑指Offer（二十五）：复杂链表的复制

剑指Offer（二十五）：复杂链表的复制

2、代码

C++：

C++
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
61
62
63
64
65
66
/*
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* pClonedHead = NULL;
        RandomListNode* pClonedNode = NULL;
        
        if(pNode != NULL){
            pClonedHead = pClonedNode = pNode->next;
            pNode->next = pClonedNode->next;
            pNode = pNode->next;
        }
        
        while(pNode != NULL){
            pClonedNode->next = pNode->next;
            pClonedNode = pClonedNode->next;
            pNode->next = pClonedNode->next;
            pNode = pNode->next;
        }
        return pClonedHead;
    }
    
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNodes(pHead);
        ConnectSiblingNodes(pHead);
        return ReconnectNodes(pHead);
    }
};

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：8   其中：访客  6   博主  2

    • avatar KodChen 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学 1
      回复 2018年3月4日 下午3:58  沙发

      递归方法是不是更简洁一些~

        • avatar Jack Cui Admin 这家伙可能用了美佬的代理 谷歌浏览器 Windows 10 美国 弗吉尼亚州
          回复 2018年3月4日 下午4:20  1层

          @KodChen 嗯，是的。可以用递归方法写一个。

        • avatar cgzjdx 来自天朝的朋友 Safari浏览器 Mac OS X 10_13_6 广东省肇庆市 鹏博士长城宽带 2
          回复 2019年3月1日 上午11:06  板凳

          您好，我有个问题，对于第三个函数RandomListNode* ReconnectNodes，其中的这一部分
          if(pNode != NULL){
          pClonedHead = pClonedNode = pNode->next;
          pNode->next = pClonedNode->next;
          pNode = pNode->next;
          }
          我把他改为
          if(pNode != NULL){
          pClonedHead = pClonedNode = pNode->next;
          pNode = pNode->next->next;
          }
          为什么在牛客网上就不能通过了呢。。我觉得这两种写法应该是一样的。

            • avatar cgzjdx 来自天朝的朋友 Safari浏览器 Mac OS X 10_13_6 广东省肇庆市 鹏博士长城宽带 2
              回复 2019年3月1日 下午4:11  1层

              @cgzjdx 我在自己电脑上写了一遍，两种写法都试了，得到的结果是一样的，不知道为什么牛客网上运行不能通过。

                • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
                  回复 2019年3月4日 下午5:02  2层

                  @cgzjdx pNode->next不管了？

              • avatar 小白 来自天朝的朋友 谷歌浏览器 Windows 10 广东省广州市 联通 1
                回复 2021年2月22日 上午9:05  地板

                python3.* 的解法，你看可行？
                a = [1,2,3,4,5]

                import copy
                result = copy.deepcopy(a)

                • avatar alex 来自天朝的朋友 谷歌浏览器 Windows 10 江苏省苏州市昆山市 电信 0
                  回复 2021年7月13日 下午4:31  4楼

                  请教下这两句：pNode->next = pCloned;pNode = pCloned->next;我的理解这个应该就是插入新节点这样一个过程，第一句看起来是把new的节点跟在原始链表head后边，第二句话没明白，感觉应该是把new的节点指向原节点的第二个节点，这里直接又把new的节点指向原节点的头节点？

                    • avatar SmallRubbish 来自天朝的朋友 QQ浏览器 Windows 10 广西来宾市 电信 0
                      回复 2021年11月9日 下午11:23  1层

                      @alex 博主您好，第三部分拆分复杂链表的if语句判断和while判断，这样一前一后的作用是什么。我怎么分析的这两个语句的结构都是原链表啊，好迷啊