leetcode 链表的复制随机和插入排序
1. 复制带随机指针的链表
这道题有一定的难度，需要好好思考
1.1 题目描述
复杂链表的复制，即深拷贝
1.1.1 接口函数
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
struct Node* copyRandomList(struct Node* head) {
}
1.2 大致框架
1.2.1 想法思路
先想想看用最普通的方法试试看
其实直接拷贝也不是不可行，但是由于新链表要确定每一个random，需要自己去链表里面找，复杂度O（N），效率就下来了，所以并不是一个好方法
如果链表中存在节点的值相同,那就更加复杂了，比如链表里面有多个7的节点，那么除了要确定random指向的是7的节点，还要确定是第几个七的节点，就更复杂了
学c++之前不太好处理，c++之后可能会好弄一点
这里尝试一下另一种方法试试看
- 拷贝节点链接在原节点的后面
- 核心过程拷贝节点的
random，怎么拷贝？指空的直接也把它指空，其它的直接把现在的random指向原random->next就可以，这就体现了连在后面一个节点上的优越性
- 把拷贝节点和原链表之间的连接给解下来，然后重新链接成新的链表
先确定好cur``copy``next三个指针，然后用malloc创建新的链表，然后进行尾插，同时为了方便尾插，要设置哨兵位头节点
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eo8RCkxq-1636797500236)(…/…/…/AppData/Roaming/Typora/typora-user-images/image-20211113102453518.png)]
尾插的时候是怎么尾插？
哨兵头不管，每次先把
copytail->next指向当前的copy
再把原链表
cur->next=next恢复回去
- 然后迭代
cur=next
1.2.2 具体步骤
-
拷贝节点挂在原节点和后面，建立对应关系
struct Node* cur=head; while(cur) { struct Node *next=cur->next; struct Node *copy=(struct Node*)malloc(sizeof(struct Node)); copy->val=cur->val; copy->next=next; cur->next=copy; copy->next=next; //往后走 cur=next; } -
random节点的处理
cur=head;
while(cur)
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
- 创建新的链表用来返回，设置哨兵位，尾插，处理返回值
cur=head;
struct Node*copyHead,*copyTail;
copyHead=copyTail=(struct Node*)malloc(sizeof(struct Node));
while(cur)
{
struct Node*copy=cur->next;
struct Node*next=copy->next;
//尾插
copyTail->next=copy;
copyTail=copyTail->next; //尾往后走
//往下走
cur->next=next;
cur=next;
}
//返回哨兵位后面的节点
struct Node *guard=copyHead;
copyHead=copyHead->next;
free(guard);
return copyHead;
1.3 整体实现
struct Node* copyRandomList(struct Node* head) {
//防空
if(head==NULL)
{
return NULL;
}
//1.拷贝节点挂在原节点和后面，建立对应关系
struct Node* cur=head;
while(cur)
{
struct Node *next=cur->next;
struct Node *copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
copy->next=next;
cur->next=copy;
copy->next=next;
cur=next;
}
//2.random节点的处理
cur=head;
while(cur)
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
//3.拷贝下来链接到一起，恢复原链表
cur=head;
struct Node*copyHead,*copyTail;
copyHead=copyTail=(struct Node*)malloc(sizeof(struct Node));
while(cur)
{
struct Node*copy=cur->next;
struct Node*next=copy->next;
//尾插
copyTail->next=copy;
copyTail=copyTail->next;
cur->next=next;
cur=next;
}
struct Node *guard=copyHead;
copyHead=copyHead->next;
free(guard);
return copyHead;
}
2. 链表的插入排序
2.1 题目描述
示例
2.1.1 接口函数
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertionSortList(struct ListNode* head){
}
2.1.2 插入排序算法
看一张来自于网络的gif解释插入排序算法
这里要理解一下区别，这里的图片虽然是从后往前比，但是单链表想想都知道是不可能的，所以自然是应该从前往后比（前提是我要排序完的链表是升序的）
2.2 大致框架
2.2.1 想法思路
- 创建三个指针
- 排序之后发现后面的比前面小的话，就是一个头插操作，把sortHead再给到新的头，然后
cur和next往后走
- 但是当碰到比头小的数就不一样了，移到对应位置发现，前一个指针找不到了，所以要做改进
- 改进：需要由一个指针来保存，这里我们就会考虑创建一个p表示前一个位置的指针，c表示当前位置指针
- 还要排除一种情况，当如下情况遇到一个5的时候，按以上想法可能c走到NULL就结束了，但是5并没有放入，所以要保证5连入，再if来保证这种情况可以实现
小结：
- 我们需要理解这些过程，其实一道题里面要实现循环要有三个条件
- 起始条件
- 终止条件
- 迭代情况
- 在这道题的插入算法中要考虑三种可能性，插入到新的链表的头前，或者中间，或者插入到最后
2.2.2 具体步骤
- 初始条件 创建指针
if(head==NULL||head->next==NULL)
{
return head;
}
//1.起始条件
struct ListNode* sortHead=head;
struct ListNode*cur=head->next;//head要指向next就要防head是空
sortHead->next=NULL;
-
终止条件当cur走完
- 分类比较
cur->val和c->val
if(cur->val<c->val) { break; } else { p=c; c=c->next; }- 不放在循环里面，一步到位，解决一次插入
if(p==NULL) { cur->next=c; sortHead=cur; } else { p->next=cur; cur->next=c; } - 分类比较
-
迭代条件
cur=next;
2.3 整体实现
struct ListNode* insertionSortList(struct ListNode* head){
if(head==NULL||head->next==NULL)
{
return head;
}
//1.起始条件
struct ListNode* sortHead=head;
struct ListNode*cur=head->next;//head要指向next就要防head是空
sortHead->next=NULL;
while(cur)//2.终止条件
{
//3.迭代条件
struct ListNode* next=cur->next;
//将cur节点插入到有序
struct ListNode*p=NULL,*c=sortHead;
while(c)
{
if(cur->val<c->val)
{
break;
}
else
{
p=c;
c=c->next;
}
}
if(p==NULL)
{
cur->next=c;
sortHead=cur;
}
else
{
p->next=cur;
cur->next=c;
}
cur=next;
}
return sortHead;
}
小结：
这次的题目也是有一点难度的，总的来说好好画图是解决这些题目的好方法，有清晰的图就会有清晰的思路
希望老铁们觉得有所收获的话给个一键三连哦