【面试题】剑指offer26--复杂链表的复制

Bertha 。 2022-06-13 08:28 130阅读 0赞

链表分很多种，（1）单链表：只有指向后一个结点的指针next

（2）双链表：有指向前一个结点的指针prev和指向后一个结点的指针next

（3）复杂链表：除了有一个指向后一个结点的指针next之外，还有一个指向任意结点或者NULL的指针Sibling

如下图所示的情形：

![Center][]

图中直线表示指向后一个结点，而虚线表示指向任意一个结点，或者NULL。

代码实现：

#include<iostream>
    using namespace std;
    #include<assert.h>
    struct Node
    {
    	Node* _value;
    	Node* _next;
    	Node* _Sibling;
    };
    Node* CopyComplexList(Node*& phead)
    {
    	assert(phead);
    	Node* Cur = phead;
    	Node* tmp = NULL;
    	while (Cur)
    	{
    		tmp = Cur;
    		Cur = Cur->_next;
    
    		Node* newNode = new Node(tmp->_value);
    		tmp->_next = newNode;
    		newNode->_next = Cur;
    	}
    
    	Cur = phead;
    	Node* newNode = NULL;
    	while (Cur)
    	{
    		newNode = Cur->_next;
    		if (Cur->_Sibling)
    		{
    			newNode->_Sibling = Cur->_Sibling->_next;
    		}
    		Cur = newNode->_next;
    	}
    	Cur = phead;
    	Node* newHead = NULL;
    	if (Cur)
    	{
    		newHead = Cur->_next;
    	}
    	Node* newCur = newHead;
    	while (Cur)
    	{
    		newCur = Cur->_next;
    		Cur->_next = newCur;
    		Cur = Cur->_next;
    	}
    	return newHead;
    }

[Center]: /images/20220613/07fdddb8568c478e9d22c5cf817a02e9.png

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer面试题26之复杂链表的复制问题

@复杂链表的定义之前实现都是单链表，单链表的结构中有数据域和指针域，而今天我们就要由单链表过渡到复杂链表。那仫什仫是复杂链表呢？首先从结构上来说复杂链表比单链表多了

谁借莪１个温暖的怀抱￠/ 2022年09月21日 15:23/ 0 赞/ 137 阅读

相关【剑指offer-Java版】26复杂链表的复制

复杂链表复制：一种思路是通过哈希表存放sibling的配对信息 – 没看明白一种思路是直接在原始链表中复制，然后拆分 – 属于时间和空间效率都比较高的方式分三步

蔚落/ 2022年08月21日 09:40/ 0 赞/ 120 阅读

相关剑指offer_面试题26_复杂链表的复制

题目：请实现函数ComplexListNode \ Clone(ComplexListNode \ pHead),复制一个复杂链表。在复杂链表中，每个结点除了有一个 m\_pN

小鱼儿/ 2022年08月04日 04:27/ 0 赞/ 146 阅读

相关剑指Offer面试题26（Java版）：复杂链表的复制

题目描述：复制一个复杂链表，在复杂链表中，每个结点除了有一个next指针指向下一个结点外，还有一个sbiling指向链表中的任意结点或者null。下图是一个复杂链表

Bertha 。/ 2022年07月16日 04:39/ 0 赞/ 151 阅读

相关【面试题】剑指offer26--复杂链表的复制

链表分很多种，（1）单链表：只有指向后一个结点的指针next （2）双链表：有指向前一个结点的指针prev和指向后一个结点的指针next （3）复杂链表：除了有一个指向

Bertha 。/ 2022年06月13日 08:28/ 0 赞/ 131 阅读

相关剑指offer面试题[26]-复杂链表的复制

题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中

忘是亡心i/ 2022年06月11日 04:17/ 0 赞/ 129 阅读

相关【剑指offer】面试题35：复杂链表的复制

题目输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点或者null），返回结果为复制后复杂链表的head

落日映苍穹つ/ 2022年06月11日 02:23/ 0 赞/ 158 阅读

相关剑指offer-题26：复杂链表的复制

题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中

电玩女神/ 2022年05月29日 13:11/ 0 赞/ 172 阅读

相关【剑指offer】面试题35：复杂链表的复制

> 题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要

朱雀/ 2022年04月10日 13:29/ 0 赞/ 184 阅读

相关 26. 复杂链表的复制《剑指Offer》(Java版)

[github地址][github] 题目描述 > 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果

水深无声/ 2022年01月30日 11:11/ 0 赞/ 147 阅读