【数据结构】(图解)leetcode刷题之单链表(下)
👋大家好呀!这个是付青云同学的博客
目前一直在学习C语言。🐸
写博客是为了来记录我的学习过程,同时也希望通过博客能够帮助到需要帮助的人。
如果我的博客可以帮助到你,不妨给我一个关注哦😁文章目录
最近在学数据结构,学了的知识后当然要巩固一下,所以就找了一些经典的链表题写一写,同时也分享一下我做题的一些思路。
#另外:这个系列文章将会有上中下三部分,难度递增
往期系列
【数据结构】(图解)leetcode刷题之单链表(上)
【数据结构】(图解)leetcode刷题之单链表(中)
环形链表
题目描述如下(具体可以点击上方链接):
思路:
使用追及法,定义快慢指针(fast,slow),fast指针每次走两步,slow指针每次走一步,如果这个链表是环形链表则两指针一定会相遇。
代码如下:
bool hasCycle(struct ListNode *head) { struct ListNode* fast,*slow; slow=fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { return true; } } return false;}
延伸问题
这里我就不证明了,大家可以自己思考思考🐸
为什么slow和fast会在环中相遇?
为什么让slow走一步,fast走两步呢?
复制带随机指针的链表
题目描述如下(具体可以点击上方链接):
思路:
- 首先,我们要向内存申请空间,插在原节点之间。
就像这样:
- 这个时候我们就要确定random,直接看图吧:
- 当新链表中的random确定后,就是将它从原链表中分离了,然后拼接成一个新链表
代码如下:
struct Node* copyRandomList(struct Node* head) { struct Node* cur=head; struct Node* copy; while(cur) { //1、复制val copy=(struct Node*)malloc(sizeof(struct Node)); copy->val=cur->val; //2、插入 copy->next=cur->next; cur->next=copy; cur=copy->next; } //3、放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; } //4、断开 struct Node* copyHead,*copyTail; copyHead=copyTail=NULL; cur=head; while(cur) { struct Node* copy=cur->next; struct Node* next=copy->next; if(copyTail==NULL) { copyHead=copyTail=copy; } else { copyTail->next=copy; copyTail=copy; } cur->next=next; cur=next; } return copyHead;}