前言

學習完畢鏈表(單雙鏈表)后,博主更新了6道比較有意思的鏈表題,并且全部配以圖解文字說明,對于大家有一定的幫助,謝謝支持哦~

01-洗掉鏈表元素

給你一個鏈表的頭節點 head 和一個整數 val ，請你洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點，

示例: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
輸出：[]

迭代法(這種操作和我們學習鏈表增刪查改時候一樣):

比較明顯,這是一個鏈表的增刪改查里面的洗掉操作.大家還記得在單鏈表里面我們要洗掉一個結點的步驟是什么嗎? 沒錯:

• 第一步: 找到需要洗掉的結點前一個結點,即如果cur->next->val等于val,說明cur就是需要洗掉結點的前一個結點
• 第二步: 讓需要洗掉結點的前一個結點 與 需要洗掉結點的后一個結點 連接,即cur->next = cur->next->next
• 第三步: 釋放需要洗掉的結點.(博主知道不釋放記憶體是一個很糟糕的習慣,但是這里只是在講解演算法題,所以博主就偷懶了)

而大致的迭達方法如下:

如果 cur的下一個節點的節點值不等于給定的 val，則保留下一個節點，將 val移動到下一個節點即可，

當 cur的下一個節點為空時，鏈表遍歷結束，此時所有節點值等于val 的節點都被洗掉

但是我們還記得嗎？在單鏈表的頭刪操作中,我們是分了情況進行討論的,即只有一個結點和多個結點時候,這就會比較麻煩,有沒有什么好的操作省去它呢? 有,這個操作就是給原來鏈表增加一個啞結點

示意圖（假設有下面一個鏈表,需要洗掉的val是6,綠色移動點代表在判斷是否等于val,橙色代表val結點后面一個結點):

題解:

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* dummynode = (struct ListNode*)malloc(sizeof(struct ListNode));  //創建啞結點
    dummynode->next = head; //連接鏈表
    struct ListNode* cur = dummynode; //迭代結點
    
    while(cur->next) //當下一個為空指標就結束
    {
        if(cur->next->val == val) //如果下一個結點的值等于val,就連接橙色結點
        {
            cur->next = cur->next->next;
        }
        else
        {
            cur = cur->next;
        }
    }
    return dummynode->next;//回傳修改后的結點(不要啞結點哦~~)
}

02-反轉鏈表

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

示例1:

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

示例2:

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

示例3:

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

我們的正常想法是,先給一個prev指標置為NULL,再給個cur指標賦值head,然后cur指向prev,最后prev和cur依次像下圖這樣迭代:

有問題嗎?問題很大,問題出在哪里了?那就是當cur指向prev后,等下一次迭代時,cur就找不到他原來后面的結點,所以說,我們還差一個指標用來保存下一個結點,上代碼:

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

03-查找鏈表中間結點

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

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

示例1:

輸入：[1,2,3,4,5]
輸出：此串列中的結點 3 (序列化形式：[3,4,5])

示例2:

輸入：[1,2,3,4,5,6]
輸出：此串列中的結點 4 (序列化形式：[4,5,6])

博主這里介紹的是快慢指標法則,即快指標比慢指標多走一步,這樣當快指標走完整個鏈表時候,慢指標就剛好是中間結點.

但有個情況是快指標的結束條件受到結點的奇偶影響.

下面我們分開進行演示:

• 當結點數是偶數時候,發現fast為空:

• 當結點數是奇數時候,發現fast為尾結點,即fast->next等于NULL:

代碼:

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast,*slow; //定義快慢指標
    fast = slow = head;
    while(fast && (fast->next))  // 當fast為空,或者fast->next為空,就結束回圈,說明此時slow已經走到了中間結點
    {
        fast = fast->next->next;//fast走兩步
        slow = slow->next; //slow走一步
    }
    return slow;
}

04-鏈表倒數第K個結點

實作一種演算法，找出單向鏈表中倒數第 k 個節點，回傳該節點的值，

示例1:

輸入： 1->2->3->4->5 和 k = 2
輸出： 4

博主這里介紹的還是快慢指標法,但是這里就需要一個變化了~~~,什么變化呢?大家想想上一個題目的快慢指標的差異是什么?

沒錯,上個題的差異是fast的速度是slow的兩倍,而我們這個題目怎么弄呢?沒錯,可以先讓fast走K步,然后slow與fast速度一樣

當fast走到末尾時候結束(fast->next等于NULL)

如圖:

代碼:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    struct ListNode* slow,*fast;
    slow = fast = pListHead;   //創建快慢指標
    
    while(k--)   //fast先走K步
    {
        if(fast)        //注意!!!!這里必須要判斷,為什么呢?因為題目并沒有規定k是小于等于鏈表長度的哦
            fast = fast->next;
        else
            return NULL;
    }
    while(fast)  //同步
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

05-合并兩個有序鏈表

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

示例1

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

示例2

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

示例3

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

如果這個題是兩個陣列,大家有沒有啥想法? 對,估計大部分的想法都是 新建立一個陣列,然后陣列上下兩兩比較,放進新陣列.

而我們鏈表其實也可以這樣,我們可以建立一個啞結點,然后讓鏈表1和鏈表2每個結點進行比較,小的就依次放在啞結點后,如圖:

代碼:

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){

    struct ListNode* p1 = l1,*p2 = l2;
    struct ListNode* newhead = NULL,*tail = NULL;

    p1 == NULL ? (return p2):(;); //后面括號是空陳述句
    p2 == NULL ? (return p1):(;);
    
    newhead = tail = (struct ListNode* )malloc(sizeof(struct ListNode)); //創建新結點

    while(p1 && p2)  //開始一一比較并進行連接
    {
        (p1-> val) <= (p2->val) ?  //比較誰小
        (tail->next = p1,p1 = p1->next,tail = tail->next) :  //p1的值更小,則連接p1,然后tail和p1迭代
        (tail->next = p2,p2 = p2->next,tail = tail->next);   //p2的值更小,則連接p2,然后tail和p2迭代
    }

    p1 ? (tail->next = p1):(p1);  //如果p1還有值,則把剩下的p1連接
    p2 ? (tail->next = p2):(p2);  //如果p2還有值,則把剩下的p2連接

    struct ListNode* pp = newhead->next;  //保存啞結點后面的結點
    free(newhead); //釋放啞結點
    newhead = NULL;
    return pp;
}

06-鏈表分割

現有一鏈表,給一定值x，撰寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的資料順序，回傳重新排列后的鏈表的頭指標，

思路:

同時創建兩個啞結點,值小于x的結點放在第一個結點后,值大于等于x的結點放在第二個結點后,等原鏈表放完后,再把第二個啞結點鏈表后面的資料連接在第一個啞結點鏈表上,具體程序如圖:

代碼:

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        if(pHead == NULL) return NULL;  //如果原鏈表是空,就回傳空
        
        ListNode* cur = pHead,*dummyone,*dummytwo,*tailone,*tailtwo,;
        tailone = dummyone = (ListNode*)malloc(sizeof(ListNode));//創建啞結點
        tailtwo = dummytwo = (ListNode*)malloc(sizeof(ListNode));
        
        while(cur) //進行迭代
        {
            cur->val < x ?
            (tailone->next = cur,tailone = tailone->next,cur = cur->next) : //小值放在dummyone鏈表
            (tailtwo->next = cur,tailtwo = tailtwo->next,cur = cur->next) ; //大值放在dummytwo鏈表
        }
        
        tailone->next = dummytwo->next;//連接
        tailtwo->next = NULL;
        
        return dummyone->next;
    }
};