現在的力扣題的源代碼我會全部一并上傳至我的碼云倉庫里面，點我看倉庫

寫在前面
首先祝各位程式猿1024狂歡節快樂鴨！這是屬于我們的節日

為了致敬1024，今天的力扣系列不再是一題了，而是多個題的組合

也是與我們最近更新的內容夢幻聯動

206題：反轉鏈表

題目描述

給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，

例如：
1->2->3->4->5
我們要回傳5->4->3->2->1

思路求解

此題我們有兩個方法求解

指標反轉法

設我們有這個鏈表

我們可以想到，要反轉鏈表，我們可以嘗試去反轉指標的指向

一個一個的反轉，直到反轉到末尾就行了

說起簡單，我們其實要考慮很多細節

1. 題目說的是單鏈表，我們不能直接找到前面的結點，所以需要一個指標指向當前指標的前面結點
2. 改變指向后，我們無法找到后面的結點了，所以還需要另外一個指標指向當前指標后面的結點

所以這里我們需要三個指標，prev，cur，next

初始化：
prev先指向空，cur指向head,next指向head->next

遍歷方法圖解：

結束條件，cur為空時，但要注意，cur為空時，不能移動next了，因為這會導致空指標解參考的錯誤，具體在代碼中說明

代碼實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    if(!head)
        return NULL;//這里是空鏈表的情況
    struct ListNode* prev=NULL,*cur=head,*next=head->next;
    while(cur)
    {
        cur->next=prev;
        prev=cur;
        cur=next;
        if(next)
            next=next->next;//這里是判斷cur是否走向末尾，走向末尾就不能移動next了
    }
    return n1;
}

頭插法

我們可以重新定義一個鏈表出來

我們從頭遍歷鏈表，并把結點頭插至新鏈表中

畫圖求解

代碼實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


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

    return newhead;
}

876題 鏈表的中間結點

題目描述

給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，

如果有兩個中間結點，則回傳第二個中間結點，

思路求解：

這是一個比較典型的快慢指標的問題，雖然思路比較簡單，但是真的不容易想到啊(默默流淚)

我們知道，一個中點在數學上什么特征？

上圖，我們顯然有2AC=AB

所以我們也利用了中點的特性

定義兩個指標fast和slow，其中fast每次走兩步，slow每次走一步

當fast走向末尾或者走向倒數第一個結點時，slow所指向的位置就是中點

黃色標記的是為什么呢？

因為我們有鏈表長度為奇數和偶數的情況

同樣，我們畫圖求解

這是偶數個結點的情況

這是奇數個結點的情況

代碼實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


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

劍指offer 22.鏈表倒數第K個結點

題目描述

輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，

例如，一個鏈表有 6 個節點，從頭節點開始，它們的值依次是 1、2、3、4、5、6，這個鏈表的倒數第 3 個節點是值為 4 的節點，

思路求解

因為單鏈表只能順著走，無法倒著走

所以我們順著這個思路思考，我們也同樣正著走

這也是一個雙指標問題

跟上一個題有異曲同工之妙

我們可以先讓fast指標先走k步，這樣的目的是保證fast和slow相差k個距離

fast走完k步后，slow和fast同時走

結束條件：fast走向鏈表的末尾

圖解

代碼實作

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
 
/**
 *
 * @param pListHead ListNode類
 * @param k int整型
 * @return ListNode類
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* fast=pListHead,*slow=pListHead;
    while(k--)
    {
        if(!fast)
        {
            return NULL;
        }
        fast=fast->next;
        
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

21 合并兩個有序鏈表

題目描述

將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，

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

思路求解

這個跟陣列的合并思路差不多，我在這篇博客中講到過

思路就是定義兩個指標分別指向兩個鏈表，然后比較大小，誰小就尾插進我們定義的新鏈表中，

結束條件是l1,l2其中一個指標指向空，然后直接鏈接剩下的結點即可

在這里，為了防止新鏈表為空帶來的種種問題，我們在這里引入一個哨兵位頭結點

畫圖求解

代碼實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(!l1)
        return l2;
    if(!l2)
        return l1;
        //上面是其實一個鏈表為空的情況
    struct ListNode* head=malloc(sizeof(struct ListNode));//開設頭結點
    struct ListNode* tail=head;//為尾插定義的
    while(l1&&l2)
    {
        if(l1->val<l2->val)
    {
        tail->next=l1;
        l1=l1->next;
        tail=tail->next;
    }
    else
    {
        tail->next=l2;
        l2=l2->next;
        tail=tail->next;
    }
    }

    if(!l1)
    {
        tail->next=l2;
    }
    if(!l2)
    {
        tail->next=l1;
    }//鏈接剩余的元素
    

    struct ListNode* newhead=head->next;
    free(head);
    return newhead;
}

點我直通1024小調查嘻嘻嘻