??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ì)和支持！??！
關(guān)注我，關(guān)注我，關(guān)注我，你們將會(huì)看到更多的優(yōu)質(zhì)內(nèi)容?。?/p>

前言

??在學(xué)完了順序表的基本知識(shí)后，我們可以通過(guò)一些習(xí)題來(lái)鞏固所學(xué)知識(shí)！

習(xí)題1：

刪除鏈表中等于給定值 val 的所有結(jié)點(diǎn)。oj鏈接

這道題目有兩種做法：

• 方法一：雙指針的遍歷，通過(guò)雙指針來(lái)查找刪除節(jié)點(diǎn)并連接后面的節(jié)點(diǎn)，但是缺點(diǎn)就是會(huì)有特殊情況需要考慮（頭刪的情況），代碼如下：
  
• 方法2：通過(guò)遍歷，將節(jié)點(diǎn)尾插到新鏈表，最后返回新鏈表，代碼如下：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode*cur=head,*newnode=NULL,*tail=NULL;
    while(cur)
    {
        if(cur->val!=val)
        {
            if(newnode==NULL)
            {
                newnode=cur;
                tail=cur;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;
            }
          cur=cur->next;
        }
        else
        {
            struct ListNode*next=cur;
            cur=next->next;
            free(next);
        }
    }
if(tail)
{
    tail->next=NULL;
}
  return newnode;
}

習(xí)題2

反轉(zhuǎn)一個(gè)單鏈表。oj鏈接

這道題也有兩種方法，

• 方法1：用三指針的方法，前兩個(gè)來(lái)改變每個(gè)節(jié)點(diǎn)的鏈接關(guān)系，最后一個(gè)節(jié)點(diǎn)用來(lái)標(biāo)記位置方便遍歷鏈表
  
  代碼如下：
  
• 方法2：取每個(gè)節(jié)點(diǎn)頭插到新鏈表：

習(xí)題3

給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。oj鏈接

??這里我們就要介紹一下快慢指針了。通過(guò)快慢指針我們可以解決很多問(wèn)題，以后都會(huì)用到。
??那么什么是快慢指針呢？
??顧名思義，快慢指針就是通過(guò)兩個(gè)不同指針步長(zhǎng)的不同來(lái)遍歷鏈表。

??這道題我們讓一個(gè)指針走兩步，一個(gè)指針走一步，當(dāng)快指針指向空或快指針的next指向空的時(shí)候，慢指針指向位置就是中間節(jié)點(diǎn)位置。

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode*slow=head,*fast=head;

    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

衍生題1：

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。oj鏈接

??其實(shí)也是快慢指針的思想，只是這里不是步長(zhǎng)的不同，而是起點(diǎn)不同：
??要尋找倒數(shù)第k個(gè)節(jié)點(diǎn)，就讓快指針的起點(diǎn)在慢指針的后k步。當(dāng)快指針指向空的時(shí)候，慢指針就指向倒數(shù)第k個(gè)節(jié)點(diǎn)。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* slow=pListHead;
    struct ListNode* fast=pListHead;
   
    while(k--)
    {
       
         if(fast==NULL)
    {
        return NULL;
    }
     fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

衍生題2：

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。oj鏈接

??這道題也是用快慢指針，即慢指針一次走一步，快指針一次走兩步，兩個(gè)指針從鏈表起始位置開始運(yùn)行，如果鏈表帶環(huán)則一定會(huì)在環(huán)中相遇，否則快指針率先走到鏈表的末尾。比如：陪女朋友到操作跑步減肥。

??那么，為什么快指針每次走兩步，慢指針走一步可以？
??假設(shè)鏈表帶環(huán)，兩個(gè)指針最后都會(huì)進(jìn)入環(huán)，快指針先進(jìn)環(huán)，慢指針后進(jìn)環(huán)。
??此時(shí)，兩個(gè)指針每移動(dòng)一次，之間的距離就縮小一步，不會(huì)出現(xiàn)每次剛好是套圈的情況，因此：在滿指針走到一圈之前，快指針肯定是可以追上慢指針的，即相遇。
代碼如下：

bool hasCycle(struct ListNode *head) 
{
    struct ListNode*fast=head,*slow=head;
    if(head==NULL||head->next==NULL)
    {
        return false;
    }
    fast=fast->next;
    while(fast!=slow)
    {
        if(fast==NULL||fast->next==NULL)
            break;
        fast=fast->next->next;
        slow=slow->next;
    }
    if(fast==slow)
    return true;
    return false;
}

習(xí)題4：

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有結(jié)點(diǎn)組成的oj鏈表

??這道題引入了哨兵位，也就是空的頭節(jié)點(diǎn)。其實(shí)，對(duì)于鏈表尾插的時(shí)候，需要判斷是否為空，比較麻煩，只要我們創(chuàng)建一個(gè)空的頭節(jié)點(diǎn)就可以避免很多情況。

??鏈表在頭插的時(shí)候我們不需要頭節(jié)點(diǎn)；
??鏈表在尾插的有空的頭節(jié)點(diǎn)會(huì)更方便。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*tail=newnode;
    tail->next=NULL;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            tail->next=list1;
            tail=list1;
            list1=list1->next;
        }
        else
        {
            tail->next=list2;
            tail=list2;
            list2=list2->next;
        }
    }

if(list1)
    tail->next=list1;
if(list2)
    tail->next=list2;

    return newnode->next;
}

習(xí)題5：

編寫代碼，以給定值x為基準(zhǔn)將鏈表分割成兩部分，所有小于x的結(jié)點(diǎn)排在大于或等于x的結(jié)點(diǎn)之前 。oj鏈接

??這道題我們創(chuàng)建兩個(gè)新鏈表（帶有哨兵位的空頭節(jié)點(diǎn)），小于的尾插到一個(gè)鏈表，大于的尾插到另外一個(gè)鏈表，最后將他們連起來(lái)即可。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        // write code here
        struct ListNode*greaternode=NULL;
        struct ListNode*lessnode=NULL,*cur=pHead;
       
        struct ListNode* gtail=greaternode,*ltail=lessnode;
        while(cur!=NULL)
        {
            if(cur->val>=x)
            {
                gtail->next=cur;
                gtail=cur;
                cur=cur->next;
                gtail->next=NULL;
            }
            else
            {
                ltail->next=cur;
                ltail=cur;
                cur=cur->next;
                ltail->next=NULL;
            }
        }
        ltail->next=greaternode->next;
        return lessnode->next;
    }
};

總結(jié)

??還是那句話，數(shù)據(jù)結(jié)構(gòu)需要多畫圖，并且對(duì)各種情況要有十足的把握才能做對(duì)題目。
??更新不易，辛苦各位小伙伴們動(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-806373.html

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