C語言實題講解快速掌握單連結串列上

2022-04-11 16:00:23

1、移除連結串列元素

連結直達：

題目：

思路：

此題要綜合考慮多種情況，常規情況就如同範例1，有多個節點，並且val不連續，但是非常規呢？當val連續呢？當頭部就是val呢？所以要分類討論

常規情況：

需要定義兩個指標prev和cur，cur指向第一個資料，prev指向cur的前一個。依次遍歷cur指向的資料是否為val，若是，則把prev的下一個節點指向cur的下一個節點上，cur=cur->next，prev跟著cur一起走，直到cur走到NULL

連續val：

當我們仔細觀察下，不難發現，在常規情況下是可以解決連續val的，但是頭部val就不可了

頭部val：

此時除了剛才定義的兩個指標prev和cur外，還要有個head指向頭部，當頭部是val時，將cur指向下一個位置，head跟著一起動，直到cur指向的資料不為val時，將head賦給prev。此時剩餘的就按常規處理即可。

程式碼如下：

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

2、反轉連結串列

連結直達：

反轉連結串列

題目：

思路：

法一：三指標翻轉方向

定義三個指標n1，n2，n3分別用來指向NULL，第一個資料，第二個資料。讓n2的next指向n1，把n2賦給n1，再把n3賦給n2，再執行n3=n3->next的操作，接下來重複上述操作，直到n2指向空即可。但是要注意，要先判斷該連結串列是否為NULL，如果是，則返回NULL，此外，還要保證當n3為空時就不要動了，直接把n3賦給n2即可。

程式碼如下：

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode*n1=NULL;
    struct ListNode*n2=head;
    struct ListNode*n3=n2->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}

法二：頭插

此法就需要再建立一個連結串列了，建立一個新的頭部newhead指向NULL，再定義一個指標cur指向原連結串列第一個資料，注意還得定義一個指標next指向cur的下一個節點。遍歷原連結串列，把節點取下來頭插到newhead所在的連結串列。每次更新newhead賦給cur，如圖所示：

程式碼如下：

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode*cur=head;
    struct ListNode*next=cur->next;
    struct ListNode*newhead=NULL;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        if(next)
        {
            next=next->next;
        }
    }
    return newhead;
}

3、連結串列的中間節點

連結直達：

連結串列的中間節點

題目：

思路：

快慢指標

這道題要注意奇偶數，如果為奇數，如範例1，那麼中間節點值就是3，反之偶數如範例2，返回第二個中間節點。此題我們定義兩個指標slow和fast都指向第一個資料的位置，區別在於讓slow一次走1步，fast一次走2步。當fast走到尾指標時，slow就是中間節點

程式碼如下：

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*slow=head;
    struct ListNode*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

4、連結串列中倒數第k個節點

連結直達：

連結串列中倒數第k個節點

題目：

思路：

快慢指標

定義兩個指標slow和fast，讓fast先走k步，再讓slow和fast同時走，當fast走到尾部時，slow就是倒數第k個，因為這樣的話slow和fast的差距始終是k個，當fast走到空時結束。此題同樣可以走k-1步，不過當fast走到尾部時結束，也就是fast的下一個節點指向空時結束，都一樣。先拿走k步舉例，如圖所示：

程式碼如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
    while(k--)
    {
        //if判斷，防止k大於連結串列的長度
        if(fast==NULL)
            return NULL;
        fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

5、合併兩個有序連結串列

連結直達：

合併兩個有序連結串列

題目：

思路：

法一：歸併（取小的尾插）--- 帶頭節點

假設新連結串列的頭叫head並指向NULL，還需要定義一個指標tail來方便後續的找尾，依次比較list1和list2節點的值，把小的放到新連結串列head上，並更新tail，再把list1或list2更新一下。當list1和list2兩個連結串列中一個走到空時，直接把剩下的連結串列所有剩下的元素拷進去即可

程式碼如下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //檢查list1或list2一開始就為NULL的情況
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode*head=NULL;
    struct ListNode*tail=head;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            if(tail==NULL)
            {
                head=tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=list1;
            }
            list1=list1->next;
        }
        else
        {
            if(tail==NULL)
            {
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=list2;
            }
            list2=list2->next;
        }
    }
    //當list1和list2其中一個走到空的情況
    if(list1==NULL)
    {
        tail->next=list2;
    }
    else
    {
        tail->next=list1;
    }
    return head;
}

法二：哨兵位的頭節點

解釋下帶頭節點：

比如說同樣一個連結串列存1，2，3。不帶頭節點只有這三個節點，head指向1。而帶頭節點的同樣存3個值，不過有4個節點，head指向頭部這個節點，這個節點不儲存有效資料

帶頭結點有如下好處，不用判斷head和tail是否為空了，也不用判斷list1和list2是否為空了，會方便不少。和上述思路一樣，取小的下來尾插，直接連結到tail後面即可。但是要注意返回的時候要返回head的next，因為題目給的連結串列是不帶頭的，而head本身指向的就是那個頭，所以要返回下一個。

程式碼如下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head = NULL, * tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->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;
        }
    }
    //當list1和list2其中一個走到空的情況
    if (list1 == NULL)
    {
        tail->next = list2;
    }
    else
    {
        tail->next = list1;
    }
    struct ListNode* list = head->next;
    free(head);
    head = NULL
        return list;
}

6、連結串列分割

連結直達：

連結串列分割

題目：

思路：

定義兩個連結串列lesshead和greaterhead。遍歷原連結串列，把 < x 的插入到連結串列1，把 > x 的插入到連結串列2，最後再把連結串列1和連結串列2連結起來。在定義兩個尾指標以跟進連結串列1和2新增元素

程式碼如下：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lessTail->next = greaterTail->next = NULL;
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            else
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        //合併
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        struct ListNode* list = lessHead->next;
        free(lessHead);
        free(greaterHead);
        return list;
    }
};

到此這篇關於C語言實題講解快速掌握單連結串列上的文章就介紹到這了,更多相關C語言單連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

C語言實題講解快速掌握單連結串列上

目錄

1、移除連結串列元素

2、反轉連結串列

3、連結串列的中間節點

4、連結串列中倒數第k個節點

5、合併兩個有序連結串列

6、連結串列分割

熱門文章