其他系列文章導(dǎo)航

Java基礎(chǔ)合集
數(shù)據(jù)結(jié)構(gòu)與算法合集

設(shè)計模式合集

多線程合集

分布式合集

ES合集

文章目錄

其他系列文章導(dǎo)航

文章目錄

前言

一、題目描述

二、題解

三、代碼

四、復(fù)雜度分析

前言

這是力扣的 2095 題，難度為中等，解題方案有很多種，本文講解我認(rèn)為最奇妙的一種。

慢慢開始鏈表的模塊了，這道題是一道非常好的隊(duì)列的例題，很有代表性。

一、題目描述

給你一個鏈表的頭節(jié)點(diǎn)?head?。刪除?鏈表的?中間節(jié)點(diǎn)?，并返回修改后的鏈表的頭節(jié)點(diǎn)?head?。

長度為?n?鏈表的中間節(jié)點(diǎn)是從頭數(shù)起第??n / 2??個節(jié)點(diǎn)（下標(biāo)從?0?開始），其中??x??表示小于或等于?x?的最大整數(shù)。

• 對于?n?=?1、2、3、4?和?5?的情況，中間節(jié)點(diǎn)的下標(biāo)分別是?0、1、1、2?和?2?。

示例 1：

輸入：head = [1,3,4,7,1,2,6]
輸出：[1,3,4,1,2,6]
解釋：
上圖表示給出的鏈表。節(jié)點(diǎn)的下標(biāo)分別標(biāo)注在每個節(jié)點(diǎn)的下方。
由于 n = 7 ，值為 7 的節(jié)點(diǎn) 3 是中間節(jié)點(diǎn)，用紅色標(biāo)注。
返回結(jié)果為移除節(jié)點(diǎn)后的新鏈表。 

示例 2：

輸入：head = [1,2,3,4]
輸出：[1,2,4]
解釋：
上圖表示給出的鏈表。
對于 n = 4 ，值為 3 的節(jié)點(diǎn) 2 是中間節(jié)點(diǎn)，用紅色標(biāo)注。

示例 3：

輸入：head = [2,1]
輸出：[2]
解釋：
上圖表示給出的鏈表。
對于 n = 2 ，值為 1 的節(jié)點(diǎn) 1 是中間節(jié)點(diǎn)，用紅色標(biāo)注。
值為 2 的節(jié)點(diǎn) 0 是移除節(jié)點(diǎn) 1 后剩下的唯一一個節(jié)點(diǎn)。

提示：

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

二、題解

2.1 方法一：快慢指針法

這個算法的目的是從鏈表中刪除中間的節(jié)點(diǎn)，而保持鏈表的其余部分不變。給定鏈表的頭結(jié)點(diǎn)?head，該方法返回刪除中間節(jié)點(diǎn)后的鏈表。

思路與算法：

1. 基本情況: 如果鏈表只有一個節(jié)點(diǎn)或者沒有節(jié)點(diǎn)，直接返回?null。
2. 雙指針法: 使用兩個指針，一個快速指針?fast?和一個慢指針?slow。開始時，fast?和?slow?都指向鏈表的頭部。
3. 移動指針: 當(dāng)?fast?指針移動到倒數(shù)第二個節(jié)點(diǎn)時（即當(dāng)前節(jié)點(diǎn)是中間節(jié)點(diǎn)的前一個節(jié)點(diǎn)），停止移動?fast?指針。同時，移動?slow?指針，使其指向下一個節(jié)點(diǎn)。
4. 刪除節(jié)點(diǎn): 將?slow.next?指向?slow.next.next，從而刪除中間節(jié)點(diǎn)。
5. 返回結(jié)果: 返回原始的頭節(jié)點(diǎn)?head。

2.2 鏈表算法的解題思路

鏈表算法的一般思路解法包括以下幾個方面：

1. 理解問題：首先，你需要理解問題的具體要求。例如，是否需要找到鏈表的長度，是否需要插入或刪除節(jié)點(diǎn)，是否需要反轉(zhuǎn)鏈表等。
2. 選擇合適的算法：根據(jù)問題的具體要求，選擇合適的算法。例如，如果需要找到鏈表的長度，可以使用快慢指針法；如果需要插入或刪除節(jié)點(diǎn)，可以使用雙指針法；如果需要反轉(zhuǎn)鏈表，可以使用迭代或遞歸方法。
3. 定義節(jié)點(diǎn)和鏈表結(jié)構(gòu)：在開始編寫代碼之前，你需要定義節(jié)點(diǎn)和鏈表的結(jié)構(gòu)。在大多數(shù)編程語言中，你可以使用類或結(jié)構(gòu)體來定義節(jié)點(diǎn)，使用指針或引用類型來定義鏈表。
4. 實(shí)現(xiàn)算法：根據(jù)選擇的算法，使用編程語言實(shí)現(xiàn)代碼。在實(shí)現(xiàn)代碼時，需要注意指針的操作，確保指針的正確指向。例如，在插入節(jié)點(diǎn)時，需要更新新節(jié)點(diǎn)和它后面節(jié)點(diǎn)的指針；在刪除節(jié)點(diǎn)時，需要更新被刪除節(jié)點(diǎn)前一個節(jié)點(diǎn)的指針，使其指向被刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)。
5. 測試和驗(yàn)證：運(yùn)行代碼，測試算法的正確性和效率。如果發(fā)現(xiàn)問題，需要對代碼進(jìn)行調(diào)試和修改。你可以使用一些測試用例來驗(yàn)證算法的正確性，例如測試空鏈表、只有一個節(jié)點(diǎn)的鏈表、有兩個節(jié)點(diǎn)的鏈表等。
6. 優(yōu)化和改進(jìn)：根據(jù)實(shí)際情況，可以對算法進(jìn)行優(yōu)化和改進(jìn)，以提高算法的效率和適用范圍。例如，可以使用哈希表來存儲每個節(jié)點(diǎn)的值和對應(yīng)的節(jié)點(diǎn)指針，以便快速查找節(jié)點(diǎn)；可以使用迭代方法來遍歷鏈表，避免使用遞歸方法導(dǎo)致的棧溢出問題。

三、代碼

3.1 方法一：快慢指針法

Java版本：

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = new ListNode(-1, head);
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

Pyhton版本：

class Solution:
    def deleteMiddle(self, head: ListNode) -> ListNode:
        if head.next is None:
            return None
        fast = head
        slow = ListNode(-1, head)
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
        slow.next = slow.next.next
        return head

C++版本：

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head->next == nullptr) {
            return nullptr;
        }
        ListNode* fast = head;
        ListNode* slow = new ListNode(-1, head);
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

Go版本：文章來源地址http://www.zghlxwxcb.cn/news/detail-803211.html

type ListNode struct {
    Val  int
    Next *ListNode
}

func deleteMiddle(head *ListNode) *ListNode {
    if head.Next == nil {
        return nil
    }
    fast := head
    slow := &ListNode{Val: -1, Next: head}
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return head
}

四、復(fù)雜度分析

4.1 方法一：快慢指針法

• 時間復(fù)雜度：?O(n)。
• 空間復(fù)雜度：?O(1)。

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)和算法】刪除鏈表的中間節(jié)點(diǎn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！