LeetCode之83. 刪除排序鏈表中的重複元素 - 個人文章詳情 - leetcode,鏈表,算法,鏈表,重複元素,HarmonyOS,後端開發 mob64ca140c3859 博客

文章目錄

83. 刪除排序鏈表中的重複元素

示例 1：
示例 2：
提示：
解題思路

問題深度分析

問題本質
核心思想
關鍵難點分析
典型情況分析
算法對比

算法流程圖

主算法流程（雙指針）
重複元素處理流程

複雜度分析

時間複雜度詳解
空間複雜度詳解

關鍵優化技巧

技巧1：雙指針算法（最優解法）
技巧2：遞歸算法
技巧3：哈希表
技巧4：優化版雙指針

邊界情況處理
測試用例設計

基礎測試
簡單情況
特殊情況
邊界情況

常見錯誤與陷阱

錯誤1：指針更新錯誤
錯誤2：邊界條件錯誤
錯誤3：循環條件錯誤

實戰技巧總結
進階擴展

擴展1：返回刪除的節點
擴展2：統計重複次數
擴展3：支持自定義重複條件

應用場景

代碼實現
測試結果
核心收穫
應用拓展
完整題解代碼

83. 刪除排序鏈表中的重複元素

給定一個已排序的鏈表的頭 head ，刪除所有重複的元素，使每個元素只出現一次。返回已排序的鏈表。

示例 1：

LeetCode之83. 刪除排序鏈表中的重複元素 - 個人文章_#算法

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

示例 2：

LeetCode之83. 刪除排序鏈表中的重複元素 - 個人文章_#leetcode_02

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

提示：

鏈表中節點數目在範圍 [0, 300] 內
-100 <= Node.val <= 100
題目數據保證鏈表已經按升序排列

解題思路

問題深度分析

這是經典的鏈表去重問題，也是雙指針算法的典型應用。核心在於保留第一個重複元素，在O(n)時間內刪除後續重複節點。

問題本質

給定已排序的鏈表，刪除所有重複元素，使每個元素只出現一次。這是一個鏈表遍歷問題，需要處理重複元素的保留。

核心思想

雙指針 + 重複元素處理：

雙指針：使用快慢指針遍歷鏈表
重複檢測：檢測連續重複的元素
節點保留：保留第一個重複元素，刪除後續重複節點
鏈表重構：重新連接鏈表

關鍵技巧：

使用curr指針遍歷鏈表
當發現重複時，跳過後續重複節點
保留第一個重複元素
正確更新指針關係

關鍵難點分析

難點1：重複元素的處理

需要準確檢測連續重複的元素
需要保留第一個重複元素
需要刪除後續重複節點

難點2：指針的更新

需要正確更新指針關係
需要處理邊界情況
需要保持鏈表的完整性

難點3：鏈表的遍歷

需要正確遍歷鏈表
需要處理空鏈表情況
需要處理單節點情況

典型情況分析

情況1：一般情況

head = [1,1,2,3,3]
過程：
1. 1,1 → 保留第一個1，刪除第二個1
2. 2 → 保留
3. 3,3 → 保留第一個3，刪除第二個3
結果: [1,2,3]

情況2：頭部重複

head = [1,1,2]
過程：
1. 1,1 → 保留第一個1，刪除第二個1
2. 2 → 保留
結果: [1,2]

情況3：無重複

head = [1,2,3,4,5]
結果: [1,2,3,4,5]

情況4：全部重複

head = [1,1,1,1,1]
結果: [1]

算法對比

算法	時間複雜度	空間複雜度	特點
雙指針	O(n)	O(1)	最優解法
遞歸	O(n)	O(n)	空間複雜度高
哈希表	O(n)	O(n)	空間複雜度高
暴力法	O(n²)	O(1)	效率較低

注：n為鏈表長度

算法流程圖

主算法流程（雙指針）

否

是

否

開始: head

curr = head

curr != nil?

返回head

檢查curr是否重複

curr重複?

跳過後續重複節點

保留curr節點

curr = curr.Next

重複元素處理流程

graph TD
    A[檢測重複元素] --> B{curr.Next != nil && curr.Val == curr.Next.Val?}
    B -->|是| C[跳過後續重複節點]
    B -->|否| D[無重複，保留節點]
    C --> E[更新curr指針]
    D --> F[更新curr指針]
    E --> G[繼續遍歷]
    F --> G

複雜度分析

時間複雜度詳解

雙指針算法：O(n)

每個節點最多被訪問一次
重複節點被一次性跳過
總時間：O(n)

遞歸算法：O(n)

遞歸深度為鏈表長度
時間複雜度相同
空間複雜度較高

空間複雜度詳解

雙指針算法：O(1)

只使用常數額外空間
原地修改鏈表
總空間：O(1)

關鍵優化技巧

技巧1：雙指針算法（最優解法）

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    
    curr := head
    
    for curr != nil {
        // 檢查curr是否重複
        if curr.Next != nil && curr.Val == curr.Next.Val {
            // 跳過後續重複節點
            curr.Next = curr.Next.Next
        } else {
            // 保留curr節點，移動到下一個
            curr = curr.Next
        }
    }
    
    return head
}

優勢：

時間複雜度：O(n)
空間複雜度：O(1)
邏輯清晰，易於理解

技巧2：遞歸算法

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    if head.Val == head.Next.Val {
        // 跳過重複節點
        return deleteDuplicates(head.Next)
    } else {
        // 保留當前節點
        head.Next = deleteDuplicates(head.Next)
        return head
    }
}

特點：使用遞歸，代碼簡潔但空間複雜度高

技巧3：哈希表

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    
    // 統計每個值的出現次數
    count := make(map[int]int)
    curr := head
    for curr != nil {
        count[curr.Val]++
        curr = curr.Next
    }
    
    // 創建新鏈表，只保留第一次出現的值
    dummy := &ListNode{}
    prev := dummy
    curr = head
    seen := make(map[int]bool)
    
    for curr != nil {
        if !seen[curr.Val] {
            seen[curr.Val] = true
            prev.Next = curr
            prev = prev.Next
        }
        curr = curr.Next
    }
    prev.Next = nil
    
    return dummy.Next
}

特點：使用哈希表記錄已出現的值，空間複雜度高

技巧4：優化版雙指針

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    
    curr := head
    
    for curr != nil && curr.Next != nil {
        if curr.Val == curr.Next.Val {
            // 跳過重複節點
            curr.Next = curr.Next.Next
        } else {
            // 移動到下一個節點
            curr = curr.Next
        }
    }
    
    return head
}

特點：優化循環條件，提前終止

邊界情況處理

空鏈表：返回nil
單節點：直接返回
全部重複：返回第一個節點
無重複：返回原鏈表
尾部重複：正確處理尾部

測試用例設計

基礎測試

輸入: head = [1,1,2,3,3]
輸出: [1,2,3]
説明: 一般情況

簡單情況

輸入: head = [1,1,2]
輸出: [1,2]
説明: 頭部重複

特殊情況

輸入: head = [1]
輸出: [1]
説明: 單節點情況

邊界情況

輸入: head = []
輸出: []
説明: 空鏈表情況

常見錯誤與陷阱

錯誤1：指針更新錯誤

// ❌ 錯誤：指針更新時機錯誤
if curr.Val == curr.Next.Val {
    curr = curr.Next // 錯誤：應該刪除重複節點
}

// ✅ 正確：刪除重複節點
if curr.Val == curr.Next.Val {
    curr.Next = curr.Next.Next
}

錯誤2：邊界條件錯誤

// ❌ 錯誤：沒有檢查邊界條件
for curr != nil {
    if curr.Val == curr.Next.Val { // 可能越界
        // ...
    }
}

// ✅ 正確：先檢查邊界條件
for curr != nil && curr.Next != nil {
    if curr.Val == curr.Next.Val {
        // ...
    }
}

錯誤3：循環條件錯誤

// ❌ 錯誤：循環條件不正確
for curr != nil {
    if curr.Next != nil && curr.Val == curr.Next.Val {
        curr.Next = curr.Next.Next
    }
    curr = curr.Next // 可能跳過節點
}

// ✅ 正確：正確的循環邏輯
for curr != nil {
    if curr.Next != nil && curr.Val == curr.Next.Val {
        curr.Next = curr.Next.Next
    } else {
        curr = curr.Next
    }
}

實戰技巧總結

雙指針模板：curr指針遍歷鏈表
重複檢測：準確檢測連續重複元素
節點刪除：正確刪除重複節點
指針更新：正確的指針更新時機
邊界處理：處理各種邊界情況

進階擴展

擴展1：返回刪除的節點

func deleteDuplicatesWithDeleted(head *ListNode) (*ListNode, []*ListNode) {
    // 返回新鏈表和刪除的節點
    // ...
}

擴展2：統計重複次數

func deleteDuplicatesWithCount(head *ListNode) (*ListNode, map[int]int) {
    // 返回新鏈表和每個值的重複次數
    // ...
}

擴展3：支持自定義重複條件

func deleteDuplicatesCustom(head *ListNode, isDuplicate func(int, int) bool) *ListNode {
    // 支持自定義重複判斷條件
    // ...
}

應用場景

數據處理：清理重複數據
鏈表優化：減少存儲空間
算法競賽：鏈表操作基礎
系統設計：數據去重
數據分析：數據清洗

代碼實現

本題提供了四種不同的解法，重點掌握雙指針算法。

測試結果

測試用例	雙指針	遞歸	哈希表	優化版
基礎測試	✅	✅	✅	✅
簡單情況	✅	✅	✅	✅
特殊情況	✅	✅	✅	✅
邊界情況	✅	✅	✅	✅

核心收穫

雙指針算法：鏈表去重的經典應用
重複檢測：準確檢測連續重複元素
節點刪除：正確刪除重複節點
指針更新：正確的指針更新時機
邊界處理：各種邊界情況的考慮

應用拓展

鏈表數據處理和清洗
算法競賽基礎
系統設計應用
數據分析技術
內存優化技術

完整題解代碼

package main

import (
	"fmt"
)

// ListNode 鏈表節點定義
type ListNode struct {
	Val  int
	Next *ListNode
}

// =========================== 方法一：雙指針算法（最優解法） ===========================

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	curr := head

	for curr != nil {
		// 檢查curr是否重複
		if curr.Next != nil && curr.Val == curr.Next.Val {
			// 跳過後續重複節點
			curr.Next = curr.Next.Next
		} else {
			// 保留curr節點，移動到下一個
			curr = curr.Next
		}
	}

	return head
}

// =========================== 方法二：遞歸算法 ===========================

func deleteDuplicates2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	if head.Val == head.Next.Val {
		// 跳過重複節點
		return deleteDuplicates2(head.Next)
	} else {
		// 保留當前節點
		head.Next = deleteDuplicates2(head.Next)
		return head
	}
}

// =========================== 方法三：哈希表 ===========================

func deleteDuplicates3(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	// 創建新鏈表，只保留第一次出現的值
	dummy := &ListNode{}
	prev := dummy
	curr := head
	seen := make(map[int]bool)

	for curr != nil {
		if !seen[curr.Val] {
			seen[curr.Val] = true
			prev.Next = curr
			prev = prev.Next
		}
		curr = curr.Next
	}
	prev.Next = nil

	return dummy.Next
}

// =========================== 方法四：優化版雙指針 ===========================

func deleteDuplicates4(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	curr := head

	for curr != nil && curr.Next != nil {
		if curr.Val == curr.Next.Val {
			// 跳過重複節點
			curr.Next = curr.Next.Next
		} else {
			// 移動到下一個節點
			curr = curr.Next
		}
	}

	return head
}

// =========================== 輔助函數 ===========================

// 創建鏈表
func createList(vals []int) *ListNode {
	if len(vals) == 0 {
		return nil
	}

	head := &ListNode{Val: vals[0]}
	curr := head

	for i := 1; i < len(vals); i++ {
		curr.Next = &ListNode{Val: vals[i]}
		curr = curr.Next
	}

	return head
}

// 鏈表轉數組
func listToArray(head *ListNode) []int {
	var result []int
	curr := head

	for curr != nil {
		result = append(result, curr.Val)
		curr = curr.Next
	}

	return result
}

// 比較兩個鏈表是否相等
func compareLists(l1, l2 *ListNode) bool {
	curr1, curr2 := l1, l2

	for curr1 != nil && curr2 != nil {
		if curr1.Val != curr2.Val {
			return false
		}
		curr1 = curr1.Next
		curr2 = curr2.Next
	}

	return curr1 == nil && curr2 == nil
}

// =========================== 測試代碼 ===========================

func main() {
	fmt.Println("=== LeetCode 83: 刪除排序鏈表中的重複元素 ===\n")

	testCases := []struct {
		nums   []int
		expect []int
	}{
		{
			[]int{1, 1, 2, 3, 3},
			[]int{1, 2, 3},
		},
		{
			[]int{1, 1, 2},
			[]int{1, 2},
		},
		{
			[]int{1},
			[]int{1},
		},
		{
			[]int{},
			[]int{},
		},
		{
			[]int{1, 1, 1, 1, 1},
			[]int{1},
		},
		{
			[]int{1, 2, 3, 4, 5},
			[]int{1, 2, 3, 4, 5},
		},
		{
			[]int{1, 1, 2, 2, 3, 3},
			[]int{1, 2, 3},
		},
		{
			[]int{1, 2, 2, 3, 3, 4},
			[]int{1, 2, 3, 4},
		},
	}

	fmt.Println("方法一：雙指針算法（最優解法）")
	runTests(testCases, deleteDuplicates)

	fmt.Println("\n方法二：遞歸算法")
	runTests(testCases, deleteDuplicates2)

	fmt.Println("\n方法三：哈希表")
	runTests(testCases, deleteDuplicates3)

	fmt.Println("\n方法四：優化版雙指針")
	runTests(testCases, deleteDuplicates4)
}

func runTests(testCases []struct {
	nums   []int
	expect []int
}, fn func(*ListNode) *ListNode) {
	passCount := 0
	for i, tc := range testCases {
		input := createList(tc.nums)
		expected := createList(tc.expect)
		result := fn(input)

		status := "✅"
		if !compareLists(result, expected) {
			status = "❌"
		} else {
			passCount++
		}
		fmt.Printf("  測試%d: %s\n", i+1, status)
		if status == "❌" {
			fmt.Printf("    輸入: %v\n", tc.nums)
			fmt.Printf("    輸出: %v\n", listToArray(result))
			fmt.Printf("    期望: %v\n", tc.expect)
		}
	}
	fmt.Printf("  通過: %d/%d\n", passCount, len(testCases))
}

本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。

博客 / 詳情