当前位置：首页 > news >正文

数据结构之加餐篇 -顺序表和链表加餐

news 2025/9/4 12:08:10

一、链表分割

链表分割
在这里插入图片描述
题目描述的意思就如下图：

也就是把1，2挪到前面，6，3，5挪到后面，前者的相对顺序不发生改变

这里要想往后挪就要先遍历，遍历到6比3小，这里要通过删除6这个节点然后尾插到后面来实现吗？这样就太麻烦了

思路：创建两个非空链表（小链表，大链表），遍历原链表，小的尾插到小链表中，大的尾插到大链表中（简单的将节点分为小于x的节点和大于等于x的节点），最终大链表和小链表首尾相连
在这里插入图片描述

注意：这里第一个参数是链表，所以我们就加一个大括号，然后节点之间用逗号分隔，两个参数之间也要用逗号分隔

这串代码看似没有问题

然而提交出现了错误，出现内存超限的原因有两种，第一种是陷入死循环，第二种是无限递归（无线创建函数栈帧），首先排除死循环，因为自测结果没有出错，那么就是节点出现问题了
这里改一下节点顺序
在这里插入图片描述

发现出现死循环，1，2，5，3，6打印完之后又从2开始打印，6拿过来尾插之后，其的next指针没有发生改变，还是指向2这个节点

解决方法很简单，让大链表的尾节点置为空就好

二、随机链表的复制

随机链表的复制
在这里插入图片描述
补充一下题目中所说的深/浅拷贝是什么意思
浅拷贝：就是值拷贝

如图将pcur指向节点3进行浅拷贝，只需要让新的指针指向3即可
如果是深拷贝就要向操作系统额外申请一个节点大小的空间

乍一看这个题很简单
在这里插入图片描述
这里定义pcur来遍历原链表，只要节点不为空，就复制该节点
首先向操作系统malloc一块一摸一样节点大小的空间

新的节点的值和原节点相等，next和random的值初始情况下置为空，接下来pcur往后走，只要节点不为空，就把13这个节点拿到复制链表进行尾插，新节点的13（next，random都默认为空），新节点7的next指针指向13
在这里插入图片描述
依次类推

但是尾插的时候只能设置当前节点里的值和next指针，这个random指针怎么做呢？
如果我再让pcur回到第一个节点，发现原链表的random指针置为空，便让新链表的random指针置为空

还需要定义一个指针遍历新的链表，也就是操作完一个节点pcur和copy都要往后走，但是发现13的random指针指向前一个节点，单链表又是单向的，这里是头节点
在这里插入图片描述
如果10的random节点指向13，这就不好找了，又要从头向后遍历

新的思路：（1）就是在原链表的基础上拷贝节点

在这里插入图片描述
从头开始遍历，遍历到7，创建一个和7一摸一样的节点（malloc），然后让newnode尾插到pcur节点之后，newndoe的next指针指向pcur的下一个节点，pcur的下一个节点用next保存

尾插之后pcur指向其原来指向的next节点，只要13这个节点不为空，再深拷贝一个13节点，然后把新的节点拿到13节点之后尾插，然后pcur->next指针指向newnode，newnode->next指针指向next节点，以此类推，循环往复
在这里插入图片描述
pcur跳出循环,不能对空节点进行深拷贝

（2）设置random指针

在这里插入图片描述
这里原链表中7的random指针置为空，那么复制节点的ramdom也置为空，然后copy往后走，cur也往后走（这里cur原来是在原节点7的位置）
原链表13的random指针是7，那么copy节点的random指针满足下面的条件，当原链表里的random指针不为空，就满足这样一个规则
在这里插入图片描述
cur->random指针指向7，其的next节点就是复制节点的random指针指向的节点

此时copy和cur都往后走，以此类推，循环往复
在这里插入图片描述
此时只要cur的random指针不为空，就可以执行该规则

当cur为空，拷贝节点的random指针都设置完了

（3）断开新旧链表

在这里插入图片描述
这里断开可以让拷贝节点指向其下一个节点，原链表的next指针其实不用管，虽然原链表的next指针指向新链表，但是并不影响新链表，新链表连到一起打印的时候，并不会打印到原链表里面

所以这里新旧链表的断开可以让新链表的next指针指向自己的节点，也可以让原链表的next指针也指向自己的节点，改不改都不影响，这里我就不管了，只要新链表是独立的链表就好了

这里拷贝链表的头和尾初始情况下指向pcur的下一个节点，只要copyTail的下一个节点不为空，就意味着pcur的下一个节点非空，让pcur走到复制节点尾节点的下一个节点，再让复制节点7的next指针不再指向原节点13，而是指向pcur的下一个节点，此时pcur的下一个节点就是新节点13，此时13称为拷贝链表的新的尾节点，这里要两张图结合来看
在这里插入图片描述
以此类推，循环往复

这里只要copyTail的下一个节点不为空，这里pcur可以走到copyTail的下一个节点，再让copyTail->next指针指向pcur的下一个节点

然后1变为新的尾节点，这里copyTail的下一个节点为空了，此时就把旧链表从新链表里面断开了。

直接返回拷贝后链表的头节点就好了

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/typedef struct Node Node;//创建新节点Node* buyNode(int x){Node* newnode=(Node*)malloc(sizeof(Node));newnode->val=x;newnode->next=newnode->random=NULL;return newnode;}//在原链表的基础上拷贝节点插入原链表中
void AddNode(Node* head)
{Node* pcur=head;while(pcur){Node* newnode=buyNode(pcur->val);Node* next=pcur->next;newnode->next=next;pcur->next=newnode;pcur=next;}
}//设置random
void setRandom(Node* head)
{Node* pcur=head;while(pcur){Node* copy=pcur->next;if(pcur->random){copy->random=pcur->random->next;}pcur=copy->next;}
}
struct Node* copyRandomList(struct Node* head) {if(head==NULL){return head;}//在原链表的基础上拷贝节点并插入到原链表中AddNode(head);//设置randomsetRandom(head);//分开新旧链表Node* pcur=head;Node* copyHead,*copyTail;copyHead=copyTail=pcur->next;while(copyTail->next){pcur=copyTail->next;copyTail->next=pcur->next;copyTail=copyTail->next;}return copyHead;
}