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

【数据结构】链表相关题目（中档题）

article 2024/12/24 20:47:12

在这里插入图片描述

🚀write in front🚀
📜所属专栏：初阶数据结构
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

在这里插入图片描述

文章目录

前言：
- 例题1：
- - 方法1：
  - 方法2：
- 例题2：
- - 完整代码：
总结

前言：

在前面的练习中，我们简单练习了链表的相关题目，今天我们在来做一些拓展！

例题1：

在这里插入图片描述

方法1：

在上一篇博客里面，我们讲述了快慢指针的概念：通过步长的差异处理环的问题。而这道题我们要寻找入口点，我们该如何处理呢？

首先，我们假设

起始点到入口的长度为L，
入口到相遇点的距离为X，
环的长度为C。

接下来我们通过快慢指针的两个性质（快指针是慢指针步数的两倍，快慢指针最后相遇）列出一个方程：
在这里插入图片描述
由得出的结论我们可以看出，如果让一个指针a从起点出发，另一个指针b从相遇点出发，如果是闭环，则他们一定会相遇！（这里我们并不需要算出n的值，因为n的值是是让a指针多走n-1个整圈，不影响和b指针相遇）。
下面我们来看看代码：

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
            struct ListNode*cur=head;
            while(cur!=slow)
            {
                cur=cur->next;
                slow=slow->next;
            }
            return slow;
        }
    }    
    return NULL;
}

方法2：

如果同学们在做题时无法自己推出这个结论，那么此时我们也可以将相遇点断开，此时就变成了寻找公共节点的题目了。
在这里插入图片描述

例题2：

对于这道题目，大家可能最先会想到计数器的方法，通过记录每个random的位置，在拷贝的链表里面找到对于位置依次连接。但是这样会导致时间复杂度非常的低下：O（N^2）

为了降低复杂度，就不得不使用另外一种方法。要降低时间复杂度，我们就希望能快速的找到原节点的拷贝节点。怎么找呢？

1.拷贝节点链接在原节点后面

2.此时拷贝节点的random就是原节点random->next

3.拷贝节点解下来，链接成新链表，最后将原链表还原。

完整代码：

struct Node* copyRandomList(struct Node* head) 
{
	//第一步
    struct Node*cur=head;
    while(cur)
    {
        struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=cur->next;

        cur->next=newnode;

        newnode->next=next;
        newnode->val=cur->val;

        cur=next;
    }
    //第二步
    cur=head;
    while(cur)
    {
        struct Node*prev=cur->next;
        if(cur->random==NULL)
        {
            prev->random=NULL;
        }
        else
        {
            prev->random=cur->random->next;
        }
        cur=cur->next->next;
    }
    //第三步
    struct Node* newhead=NULL,*newtail=NULL;
    cur=head;
    while(cur)
    {
        struct Node*prev=cur->next;
        struct Node*next=prev->next;
        if(newhead==NULL)
        {
            newhead=newtail=prev;
        }
        else
        {
            newtail->next=prev;
            newtail=prev;
        }
        cur=next;
    }
    return newhead;
}