個人主頁：點(diǎn)我進(jìn)入主頁

專欄分類：C語言初階? ? ??C語言程序設(shè)計————KTV? ? ? ?C語言小游戲? ? ?C語言進(jìn)階

C語言刷題? ? ? ?數(shù)據(jù)結(jié)構(gòu)初階

歡迎大家點(diǎn)贊，評論，收藏。

一起努力，一起奔赴大廠。

目錄

1.前言?

2.題目解析

2.1?移除鏈表元素

2.2反轉(zhuǎn)鏈表

2.3鏈表的中間結(jié)點(diǎn)

2.4鏈表中倒數(shù)第k個結(jié)點(diǎn)

2.5合并兩個有序鏈表

2.6鏈表分割

3.結(jié)語

1.前言?

? ? ? ? 在前面我們講解了一些關(guān)于鏈表的內(nèi)容，其中還有一些關(guān)于鏈表的習(xí)題，今天我們主要對這些題目進(jìn)行解析。

2.題目解析

2.1?移除鏈表元素

給你一個鏈表的頭節(jié)點(diǎn)?head?和一個整數(shù)?val?，請你刪除鏈表中所有滿足?Node.val == val?的節(jié)點(diǎn)，并返回?新的頭節(jié)點(diǎn)?。

示例 1：

輸入：head = [1,2,6,3,4,5,6], val = 6
輸出：[1,2,3,4,5]

示例 2：

輸入：head = [], val = 1
輸出：[]

示例 3：

輸入：head = [7,7,7,7], val = 7
輸出：[]

提示：

• 列表中的節(jié)點(diǎn)數(shù)目在范圍?[0, 104]?內(nèi)
• 1 <= Node.val <= 50
• 0 <= val <= 50

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode *phead=(struct ListNode*)malloc(sizeof(struct ListNode));
    phead->next=head;
    struct ListNode *p=phead;
    struct ListNode *q=phead->next;
    if(!q)
        return NULL;
    while(q)
    {
        if(q->val==val)
        {
            p->next=q->next;
            free(q);
            q=p->next;
        }
        else 
        {
            p=p->next;
            q=q->next;
        }
    }
    return phead->next;
}

? ? ? ? 在這里我們需要對鏈表看是不是空的，只有一個節(jié)點(diǎn)，有多個節(jié)點(diǎn)這些情況進(jìn)行討論，我們建立一個帶頭節(jié)點(diǎn)的節(jié)點(diǎn)，然后將這些連上，先判斷是不是空，不是空兩個指針，一個指向建立的頭節(jié)點(diǎn)，另一個指向后一個節(jié)點(diǎn)，我們針對后面的節(jié)點(diǎn)進(jìn)行判斷，值相等進(jìn)行去除?操作，最后返回頭節(jié)點(diǎn)的下一個節(jié)點(diǎn)。

2.2反轉(zhuǎn)鏈表

給你單鏈表的頭節(jié)點(diǎn)?head?，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

示例 1：

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]
輸出：[2,1]

示例 3：

輸入：head = []
輸出：[]

提示：

• 鏈表中節(jié)點(diǎn)的數(shù)目范圍是?[0, 5000]
• -5000 <= Node.val <= 5000

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *phead=(struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *p=head;
    phead->next=NULL;
    if(!p)
        return NULL;
    struct ListNode *q=p->next;
    while(p)
    {
        p->next=phead->next;
        phead->next=p;
        p=q;
        if(q)
            q=q->next;
    }
    return phead->next;
}

? ? ? ? 我們建立一個頭節(jié)點(diǎn)，然后連起來，判斷是不是為空，我們知道頭插相當(dāng)于將數(shù)據(jù)進(jìn)行反轉(zhuǎn)，所以我們可以將鏈表一次一次地拆下來，然后頭插到頭節(jié)點(diǎn)上，我們用兩個指針，一個用來記錄位置，一個用來進(jìn)行拆地操作。

2.3鏈表的中間結(jié)點(diǎn)

給你單鏈表的頭結(jié)點(diǎn)?head?，請你找出并返回鏈表的中間結(jié)點(diǎn)。

如果有兩個中間結(jié)點(diǎn)，則返回第二個中間結(jié)點(diǎn)。

示例 1：

輸入：head = [1,2,3,4,5]
輸出：[3,4,5]
解釋：鏈表只有一個中間結(jié)點(diǎn)，值為 3 。

示例 2：

輸入：head = [1,2,3,4,5,6]
輸出：[4,5,6]
解釋：該鏈表有兩個中間結(jié)點(diǎn)，值分別為 3 和 4 ，返回第二個結(jié)點(diǎn)。

提示：

• 鏈表的結(jié)點(diǎn)數(shù)范圍是?[1, 100]
• 1 <= Node.val <= 100

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

? ? ? ? 我們先對鏈表進(jìn)行判斷是不是空鏈表，然后利用快慢指針進(jìn)行操作，快指針每次走兩步，滿指針每次走一步，當(dāng)快指針為空且快指針地下一個指針不為空就進(jìn)行，知道出現(xiàn)這兩個有一個為空才停止。

2.4鏈表中倒數(shù)第k個結(jié)點(diǎn)

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

示例1

輸入：

1,{1,2,3,4,5}

復(fù)制返回值：

{5}

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

? ? ? ? 在這里我們同樣用快慢指針，我們先讓快指針走k步如果在k次中出現(xiàn)為空說明超出限制，返回空，快指針走k步后快慢指針一起走當(dāng)快指針指向空此時地慢指針就是倒數(shù)第k個節(jié)點(diǎn)。

2.5合并兩個有序鏈表

將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。?

示例 1：

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]

示例 2：

輸入：l1 = [], l2 = []
輸出：[]

示例 3：

輸入：l1 = [], l2 = [0]
輸出：[0]

提示：

• 兩個鏈表的節(jié)點(diǎn)數(shù)目范圍是?[0, 50]
• -100 <= Node.val <= 100
• l1?和?l2?均按?非遞減順序?排列

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode*phead=(struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode*s1=list1,*s2=list2,*cur=phead;
    while(s1&&s2)
    {
        if(s1->val<=s2->val)
        {
            cur->next=s1;
            cur=cur->next;
            s1=s1->next;
            cur->next=NULL;
        }
        else
        {
            cur->next=s2;
            cur=cur->next;
            s2=s2->next;
            cur->next=NULL;
        }
    }
    if(!s1)
    {
        cur->next=s2;
    }
    else{
        cur->next=s1;
    }
    return phead->next;
}

? ? ? ? 在這里我們創(chuàng)建一個頭節(jié)點(diǎn)，然后兩個指針指向這兩個鏈表，當(dāng)這兩個指針有一個為空時結(jié)束循環(huán)，循環(huán)里就是找到這兩個指針地數(shù)據(jù)哪一個小，去連上頭節(jié)點(diǎn)進(jìn)行尾插，這兩有一個為空時另外一個直接連上。

2.6鏈表分割

現(xiàn)有一鏈表的頭指針 ListNode*?pHead，給一定值x，編寫一段代碼將所有小于x的結(jié)點(diǎn)排在其余結(jié)點(diǎn)之前，且不能改變原來的數(shù)據(jù)順序，返回重新排列后的鏈表的頭指針。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here        
        ListNode *list1=(ListNode*)malloc(sizeof(ListNode));
        ListNode *list2=(ListNode*)malloc(sizeof(ListNode));
        ListNode*s1=list1,*s2=list2;
        list1->next=NULL;
        list2->next=NULL;
        ListNode*p=pHead;
        while(p)
        {
            if(p->val<x)
            {
                s1->next=p;
                p=p->next;
                s1->next=NULL;
            }
            else 
            {
                s2->next=p;
                p=p->next;
                s2->next=NULL;
            }
        }
        s1->next=list2->next;
        free(list2);
    return list1->next;

}

? ? ? ? 我們創(chuàng)建兩個頭節(jié)點(diǎn)，然后將小于x的放在一個鏈表上，大于等于X的放在另一個鏈表，最后連起來。

3.結(jié)語

? ? ? ? 數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)非常的重要，我們想要學(xué)習(xí)好數(shù)據(jù)結(jié)構(gòu)需要我們多多的刷題，希望大家可以在平時多多刷題來提升自己，最后希望大家可以三連一下文章來源地址http://www.zghlxwxcb.cn/news/detail-754102.html

到了這里，關(guān)于C/C++數(shù)據(jù)結(jié)構(gòu)之鏈表題目答案與解析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！