👋大家好呀！这个是付青云同学的博客
目前一直在学习C语言。🐸
写博客是为了来记录我的学习过程，同时也希望通过博客能够帮助到需要帮助的人。
如果我的博客可以帮助到你，不妨给我一个关注哦😁

文章目录

• • 往期系列
• 环形链表
• • 延伸问题
  • • 为什么slow和fast会在环中相遇？
    • 为什么让slow走一步，fast走两步呢？
• 复制带随机指针的链表

最近在学数据结构，学了的知识后当然要巩固一下，所以就找了一些经典的链表题写一写，同时也分享一下我做题的一些思路。
#另外：这个系列文章将会有上中下三部分，难度递增

往期系列

【数据结构】（图解）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走两步呢？

复制带随机指针的链表

题目描述如下（具体可以点击上方链接）：

思路：

1. 首先，我们要向内存申请空间，插在原节点之间。
   就像这样：
   
2. 这个时候我们就要确定random，直接看图吧：
   
3. 当新链表中的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;}

完

耳机推荐