题目:实现函数complextListNode* clone(ComplexListNoe* pHead),复制一个链表。
在复制链表中,每一个节点除了有一个m_pNext指针指向向下一个节点外,还有一个
指针m_pSibling指向链表中的任意节点或者NULL
节点定义如下:
struct ComplexListNode
{
int m_nValue;
ComplexLstNode* m_pNext;
ComplexListNode* m_pSibling;
};
思想:
空间换时间。
第一步:
根据原始链表的每一个节点N创建对应的N‘。这一次,把N’连接在N的后面
第二步:
设置复制出来的节点的m_pSibling。假设原始链表上的N的m_pSibling指向的
节点是S,那么其对应复制出来的N‘是N的m_pNext指向的节点。同样S’是S的m_pNext指向
的节点
第三步:
把这个长链表拆分成两个链表,奇数位置的节点用m_pNext连接起来就是
原始链表,把偶数节点用m_pNext连接起来就是复制出来 的链表
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
struct ComplexListNode
{
int m_nValue;
ComplexListNode* m_pNext;
ComplexListNode* m_pSibling;
} ;
//第一步 复制链表节点
void cloneNodes(ComplexListNode* pHead)
{
ComplexListNode* pNode = pHead;
while(pNode!=NULL)
{
ComplexListNode* pCloned =(ComplexListNode*)malloc(sizeof(ComplexListNode));
pCloned->m_nValue=pNode->m_nValue;
pCloned->m_pNext=pNode->m_pNext;
pCloned->m_pSibling=NULL;//复制刚开始m_pSibling设置为NULL
pNode->m_pNext=pCloned;
pNode = pCloned->m_pNext;
}
}
//第二步 连接兄弟节点
void connextSiblingNodes(ComplexListNode* pHead)
{
ComplexListNode* pNode=pHead;
while(pNode!=NULL)
{
ComplexListNode* pCloned =pNode->m_pNext;
if(pNode->m_pSibling!=NULL)
{
pCloned->m_pSibling=pNode->m_pSibling->m_pNext;
pNode=pCloned->m_pNext;
}
}
}
//第三步 分解链表 奇数节点是原链表节点 偶数节点构成新链表节点
ComplexListNode* reconnectNodes(ComplexListNode* pHead)
{
ComplexListNode* pNode=pHead;
ComplexListNode* pClonedHead=NULL;//新链表的头结点
ComplexListNode* pClonedNode=NULL;
if(pNode!=NULL)
{
pClonedHead=pClonedNode=pNode->m_pNext;
pNode->m_pNext=pClonedNode->m_pNext;
pNode=pNode->m_pNext;
}
while(pNode!=NULL)
{
pClonedNode->m_pNext=pNode->m_pNext;
pClonedNode=pClonedNode->m_pNext;
pNode->m_pNext=pClonedNode->m_pNext;
pNode=pNode->m_pNext;
}
return pClonedHead;
}
//三步结合起来
ComplexListNode* clone(ComplexListNode* pHead)
{
cloneNodes(pHead);
connextSiblingNodes(pHead);
return reconnectNodes(pHead);
}
//打印链表
void printList(ComplexListNode* pHead)
{
ComplexListNode* pCur=pHead;
while(pCur)
{
printf("%d",pCur->m_nValue);
if(pCur->m_pSibling)
{
printf("%d\n",pCur->m_pSibling->m_nValue);
}
else
{
printf("0\n");
}
pCur=pCur->m_pNext;
}
printf("\n");
}
//创建链表
ComplexListNode* createList()
{
int nLen=0;
int nSiblingData=0;//兄弟节点的结点值
scanf("%d",&nLen);
ComplexListNode* pHead=NULL;
ComplexListNode* pNew=NULL;
ComplexListNode* pLast=NULL;
for(int i=0;i<nLen;i++)
{
pNew=(ComplexListNode*)malloc(sizeof(ComplexListNode));
scanf("%d",&pNew->m_nValue);
pNew->m_pNext=NULL;
pNew->m_pSibling=NULL;
if(pHead==NULL)
pHead=pNew;
else
pLast->m_pNext=pNew;
pLast=pNew;
}
ComplexListNode* pCur=pHead;
ComplexListNode* pCurTmp=pHead;
while(pCur)
{
scanf("%d",&nSiblingData);
pCurTmp=pHead;
if(nSiblingData==0)
pCur->m_pSibling=NULL;
else
{
while(pCurTmp&&nSiblingData!=pCurTmp->m_nValue)
pCurTmp=pCurTmp->m_pNext;
assert(pCurTmp);
pCur->m_pSibling=pCurTmp;
}
pCur=pCur->m_pNext;
}
return pHead;
}
int main()
{
ComplexListNode* pHead=NULL;
ComplexListNode* pNewHead=NULL;
pHead=createList();
printList(pHead);
pNewHead = clone(pHead);
printList(pHead);
return 0;
}
结果:
分享到:
相关推荐
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会...
python 实现 复杂链表的复制
今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表。 复杂链表的数据结构如下: typedef int DataType; //数据域的类型 //复杂链表的数据结构 typedef struct ComplexNode { DataType _data ; // ...
java基础面试题复杂链表的复制本资源系百度网盘分享地址
剑指 Offer 35. 复杂链表的复制标签:哈希表、链表难度:中等题目大意给定一个链表,每个节点除了 next 指针之后,还包含一个随机指针 random,该
示例 1:// Definition for a Node.Node* copyRandomList(Node* head) {//(1)拷贝数据struct
剑指 Offer 35. 复杂链表的复制python(csdn)————程序
1、遍历链表,复制每个结点,如复制结点A得到A1,将结点A1插到结点A后面 2、重新遍历链表,复制老结点的随机指针给新结点,如A1.random = A.ran
三步走:1. 首先克隆节点,接在原节点后面3. 把新链表和原链表拆出来RandomListNode* node=pHead;RandomListNode *cl
剑指Offer(Python多种思路实现):复杂链表的复制 面试35题: 题目:复杂链表的复制 题:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为...
所以,我们需要在一开始把所有的节点都创建出来,避免 random 找不到指向,每个节点都对应着一个新的节点,原链表中的节点有 val、next、random 三
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
主要介绍了Java面试题-实现复杂链表的复制代码分享,小编觉得还是挺不错的,具有参考价值,需要的朋友可以了解下。
主要为大家详细介绍了C语言之复杂链表的复制,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, ...
4:一般的处理新建一些节点,链表都能实现这个功能;但是为了节省空间复杂度,一般尽量利用单一变量在原链表上做出修改。除非有些情况无法处理,新建数组或者链表存储数据。 5:所以对于新建链表,一般仍然...
剑指 Offer 35. 复杂链表的复制图解 链表的深拷贝剑指 Offer 35. 复杂链表的复制(哈希表 / 拼接与拆分,清晰图解)看了dfs的题解,感觉df
复杂链表的复制.py 二叉搜索树与双向链表.py 序列化二叉树.py 字符串的排列.py 数组中出现次数超过一半的数字.py 最小的k个数.py 连续子数组的最大和.py n整数中1出现的次数.py 数字序列中的某一位数字.py 把数组拍...
链表的难点在于必须复制链表处理函数来处理不同的对象,即便逻辑是完全相同的。 基础 让我们从一个非常简单的例子开始,如下: int n; 这个应该被理解为“declare n as an int”(n是一个int型的变量)...