目錄

?文章來源地址http://www.zghlxwxcb.cn/news/detail-833445.html

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

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

3.變形題：找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

4.經(jīng)典題：將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

結(jié)語(yǔ)

個(gè)人主頁(yè)：大耳朵土土垚-CSDN博客

所屬專欄：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記

?

1.給你一個(gè)鏈表的頭節(jié)點(diǎn)?head?和一個(gè)整數(shù)?val?，請(qǐng)你刪除鏈表中所有滿足?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]

解題思路：

創(chuàng)建指針遍歷鏈表找到對(duì)應(yīng)節(jié)點(diǎn)刪除；

創(chuàng)建兩個(gè)指針變量cur和pre用來記錄，cur表示當(dāng)前遍歷的節(jié)點(diǎn)，pre表示上一個(gè)節(jié)點(diǎn)如圖所示

不要忘了有兩種情況，當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)就是對(duì)應(yīng)節(jié)點(diǎn)時(shí)需要將頭指針head改變?；

如果忘記第一種情況就會(huì)發(fā)現(xiàn)以下示例：

圖中null就是指pre為空指針的情況；

以下是完整代碼實(shí)現(xiàn)：?

struct ListNode {
    int val;
    struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* pre = NULL;
    while (cur)
    {
        if (cur->val == val)//找到val值相同的節(jié)點(diǎn)時(shí)
        {
            if (pre == NULL)//如果是第一個(gè)節(jié)點(diǎn)，也就是圖中第②種
            {
                cur = head->next;
                free(head);
                head = cur;
            }
            else//其他情況
            {
                pre->next = cur->next;
                free(cur);
                cur = pre->next;
            }
        }
        else//不相同時(shí)
        {
            pre = cur;
            cur = cur->next;
        }
    }
    return head;
}

另外一種思路：

遍歷鏈表，把不是val節(jié)點(diǎn)拿出來尾插，這里就不細(xì)講有興趣的可以打在評(píng)論區(qū)或私信我哦~

代碼如下：

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

        }
        else
        {
            struct ListNode* pos = cur;
            cur = cur->next;
            free(pos);
        }
    }

    return newhead;
}

?

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

解題思路：

給fast，slow兩個(gè)指針，fast走兩步，slow走一步?,當(dāng)fast走到尾時(shí)，slow恰好走到中間。

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

?

3.變形題：找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

解題思路：

還是快慢指針，只要fast與slow之間距離為k，那么當(dāng)fast走到終點(diǎn)時(shí)，slow所在的節(jié)點(diǎn)就是倒數(shù)第k個(gè)節(jié)點(diǎn)

?

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
struct ListNode* fast = pListHead,*slow = pListHead;
 for(int i = 0; i < k; i++)//先讓fast走k步
    {
        if(fast == NULL)//如果k大于鏈表長(zhǎng)度記得要及時(shí)返回哦
         return NULL;
        fast = fast->next;
    
    }
while(fast)
{
   
    fast = fast->next;
    slow = slow->next;
}
return slow;
}

先讓fast走k步拉開距離，然后fast與slow一起走，當(dāng)fast為空指針時(shí)，slow即為倒數(shù)第k個(gè)節(jié)點(diǎn)；

?

?

4.經(jīng)典題：將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

解題思路：

? ? 取小的尾插

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {

    struct ListNode* head = NULL,*tail = NULL;
     if(list1 == NULL)//注意有鏈表為空的情況，直接返回另一個(gè)鏈表
        return list2;
    if(list2 == NULL)
        return list1;
    while(list1 && list2)//注意這里是一個(gè)鏈表結(jié)束就都結(jié)束，所以兩個(gè)都要為真用&&
    {
     if(list1->val <= list2->val)
     {
         if(head == NULL)
         {
             head = tail = list1;
         }
         else
         {
             tail->next = list1;
             tail = tail->next;
         }
         list1= list1->next;
     }
     else
     {  if(head == NULL)
         {
             head = tail = list2;
         }
         else
         {
             tail->next = list2;
             tail = tail->next;
         }
         list2= list2->next;
     }
    }
    if(list1 == NULL)
    {
        tail->next = list2;
    }
    else
    {
        tail->next = list1;
    }
    return head;
}

?要注意當(dāng)有鏈表為空的情況，以及取小結(jié)束后的情況；

?

結(jié)語(yǔ)

鏈表尾插，我們可以用一個(gè)tail指針來記錄尾插后的節(jié)點(diǎn)，尾插直接在tail節(jié)點(diǎn)后即可，這樣就不用每次尾插都循環(huán)遍歷，大大減少了時(shí)間復(fù)雜度?，提高了運(yùn)行效率。大家如果有什么問題或者想法歡迎打在評(píng)論區(qū)或私信我哦~

?

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