??write in front??
??所屬專欄：初階數(shù)據(jù)結(jié)構(gòu)
???博客主頁(yè)：睿睿的博客主頁(yè)
???代碼倉(cāng)庫(kù)：??VS2022_C語(yǔ)言倉(cāng)庫(kù)
??您的點(diǎn)贊、關(guān)注、收藏、評(píng)論，是對(duì)我最大的激勵(lì)和支持?。。?br>關(guān)注我，關(guān)注我，關(guān)注我，你們將會(huì)看到更多的優(yōu)質(zhì)內(nèi)容??！

前言：

??在前面的練習(xí)中，我們簡(jiǎn)單練習(xí)了鏈表的相關(guān)題目，今天我們?cè)趤?lái)做一些拓展！

例題1：

在這里插入圖片描述

方法1：

??在上一篇博客里面，我們講述了快慢指針的概念：通過(guò)步長(zhǎng)的差異處理環(huán)的問(wèn)題。而這道題我們要尋找入口點(diǎn)，我們?cè)撊绾翁幚砟兀?/p>

首先，我們假設(shè)

• 起始點(diǎn)到入口的長(zhǎng)度為L(zhǎng)，
• 入口到相遇點(diǎn)的距離為X，
• 環(huán)的長(zhǎng)度為C。

接下來(lái)我們通過(guò)快慢指針的兩個(gè)性質(zhì)（快指針是慢指針步數(shù)的兩倍，快慢指針最后相遇）列出一個(gè)方程：

??由得出的結(jié)論我們可以看出，如果讓一個(gè)指針a從起點(diǎn)出發(fā)，另一個(gè)指針b從相遇點(diǎn)出發(fā)，如果是閉環(huán)，則他們一定會(huì)相遇?。ㄟ@里我們并不需要算出n的值，因?yàn)閚的值是是讓a指針多走n-1個(gè)整圈，不影響和b指針相遇）。
下面我們來(lái)看看代碼：

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：

??如果同學(xué)們?cè)谧鲱}時(shí)無(wú)法自己推出這個(gè)結(jié)論，那么此時(shí)我們也可以將相遇點(diǎn)斷開(kāi)，此時(shí)就變成了尋找公共節(jié)點(diǎn)的題目了。

例題2：

對(duì)于這道題目，大家可能最先會(huì)想到計(jì)數(shù)器的方法，通過(guò)記錄每個(gè)random的位置，在拷貝的鏈表里面找到對(duì)于位置依次連接。但是這樣會(huì)導(dǎo)致時(shí)間復(fù)雜度非常的低下：O（N^2）

為了降低復(fù)雜度，就不得不使用另外一種方法。要降低時(shí)間復(fù)雜度，我們就希望能快速的找到原節(jié)點(diǎn)的拷貝節(jié)點(diǎn)。怎么找呢？

1.拷貝節(jié)點(diǎn)鏈接在原節(jié)點(diǎn)后面

2.此時(shí)拷貝節(jié)點(diǎn)的random就是原節(jié)點(diǎn)random->next

3.拷貝節(jié)點(diǎn)解下來(lái)，鏈接成新鏈表，最后將原鏈表還原。

完整代碼：

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;
}

總結(jié)

??鏈表的相關(guān)題目到這里就結(jié)束了，當(dāng)然同學(xué)們也可以去oj看看其他題：oj題
??更新不易，辛苦各位小伙伴們動(dòng)動(dòng)小手，??三連走一走???? ~ ~ ~ 你們真的對(duì)我很重要！最后，本文仍有許多不足之處，歡迎各位認(rèn)真讀完文章的小伙伴們隨時(shí)私信交流、批評(píng)指正！

專欄訂閱：
每日一題
c語(yǔ)言學(xué)習(xí)
算法
智力題
初階數(shù)據(jù)結(jié)構(gòu)
更新不易，辛苦各位小伙伴們動(dòng)動(dòng)小手，??三連走一走???? ~ ~ ~ 你們真的對(duì)我很重要！最后，本文仍有許多不足之處，歡迎各位認(rèn)真讀完文章的小伙伴們隨時(shí)私信交流、批評(píng)指正！

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-813943.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】鏈表相關(guān)題目（中檔題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！