题目:已知一链表,每个节点除了有一个指向下一节点的指针外,还有一随机指针指向链表中的任意节点(可能为空,也有可能为自身),请复制一个链表,要求节点的顺序以及节点上的随机指针指向的节点位置和原链表一致。
这个题目有个很巧妙的解法,可以达到O(n)的效率,其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表,然后给复制链表中每个节点的随机指针复制,最后再打断链表恢复原样。
typedef struct Node {
int nData;
Node* pNext;
Node* pRandom;
} Node;
Node* DuplicateList(Node* pSrcListHead)
{
if (pSrcListHead == NULL)
return NULL;
Node* pNode = pSrcListHead;
while (pNode != NULL)
{
Node* pNewNode = new Node;
pNewNode->nData = pNode->nData;
pNewNode->pNext = pNode->pNext;
pNewNode->pRandom = pNode->pRandom;
pNode->pNext = pNewNode;
pNode = pNewNode->pNext;
}
Node* pDestListHead = pSrcListHead->pNext;
pNode = pSrcListHead;
while (pNode != NULL)
{
pNode->pNext->pRandom = pNode->pRandom->pNext;
pNode = pNode->pNext->pNext;
}
pNode = pSrcListHead;
Node* pNode2 = pNode->pNext;
while (pNode != NULL)
{
pNode->pNext = pNode2->pNext;
pNode = pNode->pNext;
if (pNode)
pNode2->pNext = pNode->pNext;
else
pNode2->pNext = NULL;
pNode2 = pNode2->pNext;
}
return pDestListHead;
}
不过目前还未考虑到原始链表有环的情况,如果原始链表有环,则应该先求出环的入口点,然后利用上面的方法进行链表复制。
原文地址:http://hi.baidu.com/%B3%A3%D1%C5%C3%F4/blog/item/173d50ae523a0ede7dd92a63.html
分享到:
相关推荐
//第8题:复制链表。输入:一个无序正整数链表(输入为0表示终止)。 //输出:三行,每行一个链表,分别满足题目中的三个链表的要求。 //这道题目必须要复制链表,所以说,不能直接将输入的链表作为第一小题的输出,...
使用随机指针复制链表 给出一个链表,使得每个节点都包含一个额外的随机指针,该指针可以指向链表中的任何节点或为空。 返回列表的深层副本。 链表在输入/输出中表示为 n 个节点的列表。 每个节点都表示为一对 [val,...
首先,参数为一个pHead,要求我们能够复制链表。 我们先来看看其他大佬的做法(转自牛友chancy) 逻辑很强,值得学习。 /* *解题思路: *1、遍历链表,复制每个结点,如复制结点A得到A1,将结点A1插到结点A后面; *2...
实现整数链表的建立,其中还有复制链表的过程
简介:给你一个长度为n的链表,每个节点包含一个额外增加的随机指针random,该指针可以指向链表中的任何节点或空节点。返回复制链表的头节点。题解 1 - typ
有一个链表L,其中每个节点包含1 个数据域和2 个指针。一个指针next 指 向链表的下个节点,另一个random 随机指向...要求编写一个程序,首先完成链表的构造,然后复制这个链表的结构,新的链表具有和原链表相同的结构。
链表的难点在于必须复制链表处理函数来处理不同的对象,即便逻辑是完全相同的。 基础 让我们从一个非常简单的例子开始,如下: int n; 这个应该被理解为“declare n as an int”(n是一个int型的变量)...
python 实现 复杂链表的复制
复制带随机指针的链表1
C语言——链表技术实现的学生信息管理。直接把txt文档中的代码复制到vc++ 6.0中即可。
讲述c语言如何实现双链表首先利用双链表的一些运算建立一个空的双链表 从已有的单链表s1第一个节点开始,将信息复制到空的双链表上(一个循环)
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字...为了尽可能少的消耗复制时占用的空间,桶的数据结构选择链表,为了构造队列,选择使用双向列表。
复制带随机指针的链表.md
一、实验题目:循环链表的实现 二、实验目的: 1、实现循环表中插入函数add和addlast函数 2、实现循环表中的复制函数duplicate函数,查找元素函数includes,判空...2、循环链表的复制duplicate函数: 时间复杂度是O(n)
java基础面试题复杂链表的复制本资源系百度网盘分享地址
1、遍历链表,复制每个结点,如复制结点A得到A1,将结点A1插到结点A后面 2、重新遍历链表,复制老结点的随机指针给新结点,如A1.random = A.ran
链表的难点在于必须复制链表处理函数来处理不同的对象,即便逻辑是完全相同的。 基础 让我们从一个非常简单的例子开始,如下: int n; 这个应该被理解为“declare n as an int”(n是一个int型的变量)...
示例 1:// Definition for a Node.Node* copyRandomList(Node* head) {//(1)拷贝数据struct
带表头结点(存放的是该线性链表的长度),结点存放的是整型数值; 实现以下操作 : ... 写出类的构造函数、复制构造函数及析构函数 编写一个函数,使用户通过选择进行相关链表操作。
三步走:1. 首先克隆节点,接在原节点后面3. 把新链表和原链表拆出来RandomListNode* node=pHead;RandomListNode *cl