复杂链表的复制
程序员文章站
2022-06-11 20:17:23
...
首先我们要搞清楚一个问题,什么是复杂链表呢?
或许有的人并没有听过这个词,这个并不奇怪,对于像我这种小菜鸟来说,可能还有好多没听过的知识点呢!复杂链表的复制我也是昨天花了一天的时间才搞明白(嘿嘿,可能是因为我有点笨吧!)。
在复杂链表中,除了有一个next指针指向下一个结点,还有一个random指针指向任意结点或NULL。
eg:
对复杂链表进行复制时,必须对其random域进行复制,但是random域具有随机性,一般不容易复制,我们可以采用以下方法对复杂链表进行复制:
1.在原链表每个结点后插入与每个结点值相等的新结点
2.给新结点随即指针域random赋值
在这一步,我们需要注意的是:当pre->random == NULL时,令cur->random = NULL。
3.将新结点从原链表中拆下来
代码如下:
ComplexLinkList.h //头文件
#ifndef __COMPLEXLINKLIST_H__
#define __COMPLEXLINKLIST_H__
#include<stdio.h>
typedef int DataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* random;
DataType data;
}Node, *pNode, *pList;
pNode BuyNode(DataType d);
pNode CopyComplexLinkList(pList plist);
#endif //__COMPLEXLINKLIST_H__
ComplexLinkList.c //源文件
#include"ComplexLinkList.h"
pNode BuyNode(DataType d)
{
pNode newNode = (pNode)malloc(sizeof(Node));
if (newNode)
{
newNode->data = d;
newNode->next = NULL;
newNode->random = NULL;
return newNode;
}
else
{
printf("创建节点失败\n");
return NULL;
}
}
pNode CopyComplexLinkList(pList plist)
{
//1.在原链表每个结点后插入值相等的新结点
pNode pre = plist;
pNode NewNode = NULL;
pNode cur = NULL;
while (pre)
{
NewNode = BuyNode(pre->data);
NewNode->next = pre->next;
pre->next = NewNode;
pre = NewNode->next;
}
//2.给新结点随机指针域赋值
pre = plist;
while (pre)
{
cur = pre->next;
if (NULL == pre->random)
cur->random = NULL;
else
cur->random = pre->random->next;
pre = cur->next;
}
//3.将新结点从原链表中拆下来
pre = plist;
pNode pre2 = pre->next;//新链表的头
pNode next = pre->next;
while (next)
{
pre->next = next->next;
pre = next;
next = pre->next;
}
return pre2;
}
test.c //测试文件
#include"ComplexLinkList.h"
void ComplexLinkList_test()
{
Node node1, node2, node3, node4;
node1.data = 1;
node1.next = &node2;
node1.random = &node3;
node2.data = 2;
node2.next = &node3;
node2.random = &node1;
node3.data = 3;
node3.next = &node4;
node3.random = &node3;
node4.data = 4;
node4.next = NULL;
node4.random = NULL;
pNode ret = CopyComplexLinkList(&node1);
}
int main()
{
ComplexLinkList_test();
return 0;
}