LeetCode 83刪除排序鏈表中的重復元素 Remove Duplicates from Sorted ListGo 題解【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文圍繞 LeetCode 第 83 題“Remove Duplicates from Sorted List”展開基于本倉庫LeetCode-Go中該題目的完整實現與測試用例從題目語義、解題思路、源碼逐行剖析到復雜度分析系統講解如何在 Go 中刪除有序鏈表中的重復結點。讀完本文你將掌握單指針遍歷有序鏈表去重的核心手法并學會如何在本倉庫中運行該題對應的單元測試進行驗證。題目回顧Given a sorted linked list, delete all duplicates such that each element appear only once.題目要求給定一個已排序的鏈表刪除所有重復的結點使得每個元素只出現一次。注意兩個前提條件——鏈表本身有序、只要求刪除重復值而非保留唯一性計數這決定了題目可以用線性掃描輕松解決。示例 1Input: 1-1-2 Output: 1-2示例 2Input: 1-1-2-3-3 Output: 1-2-3題目大意刪除鏈表中重復的結點以保障每個結點只出現一次。由于鏈表有序所有重復值必然連續相鄰因此只需比較相鄰結點即可完成去重無需借助哈希表等額外數據結構。解題思路本題的核心思路是“按照題意做即可”——維護一個指針cur從頭結點開始遍歷只要cur還有下一個結點就比較cur.Next.Val與cur.Val若相等說明存在重復值直接將cur.Next指向cur.Next.Next跳過重復結點若不相等指針cur正常前移。整個過程只需遍歷一遍鏈表原地修改結點指針不需要新建鏈表也不需要額外的存儲空間。源碼實現與逐行剖析本倉庫中該題的實現位于 83. Remove Duplicates from Sorted List.go完整代碼如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // ListNode define type ListNode structures.ListNode /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func deleteDuplicates(head *ListNode) *ListNode { cur : head if head nil { return nil } if head.Next nil { return head } for cur.Next ! nil { if cur.Next.Val cur.Val { cur.Next cur.Next.Next } else { cur cur.Next } } return head }鏈表結點定義代碼開頭的type ListNode structures.ListNode是一個類型別名直接復用倉庫公共包structures中定義的鏈表結點。真正的結點定義位于 ListNode.go// ListNode 是鏈接節點 // 這個不能復制到*_test.go文件中。會導致Travis失敗 type ListNode struct { Val int Next *ListNode }每個結點包含一個整型值Val和一個指向后繼結點的指針Next與 LeetCode 官方對單鏈表結點的定義完全一致。邊界條件處理cur : head if head nil { return nil } if head.Next nil { return head }函數先處理兩種邊界情況空鏈表head nil直接返回nil僅一個結點head.Next nil不存在重復可能直接返回原鏈表。這兩步保證了后續循環中cur與cur.Next的安全訪問避免空指針解引用。去重主循環for cur.Next ! nil { if cur.Next.Val cur.Val { cur.Next cur.Next.Next } else { cur cur.Next } } return head這是算法的核心值得逐行拆解循環條件cur.Next ! nil確保每次比較都有“當前結點”與“下一結點”這一對相鄰結點當cur.Next.Val cur.Val時說明下一結點是重復值。此時執行cur.Next cur.Next.Next即跳過重復結點把當前結點的后繼指針直接指向下下個結點。注意這里指針cur不移動因為跳過一個結點后新的cur.Next仍可能與cur.Val相同例如1-1-1這種連續多個重復值需要繼續比較當值不相等時cur cur.Next指針正常前進進入下一組相鄰結點。一個關鍵設計點是跳過重復結點時cur保持原地不動。以1-1-2為例cur指向第一個1發現下一個也是1于是cur.Next直接指向2此時循環繼續cur.Next值為2與cur.Val值為1不相等cur前移指向2循環結束輸出1-2。若在跳過結點時貿然前移cur就會漏判連續三個以上重復值的情況如1-1-1。為什么“按題意做”就夠了鏈表已排序這一前提決定了所有相同值在鏈表中是連續成片存在的。因此去重等價于“把連續相同值的片段壓縮為一個結點”只需要一次線性掃描比較相鄰結點即可無需像 0082.Remove-Duplicates-from-Sorted-List-II 那樣額外記錄重復值并整段刪除那道題要求刪除所有重復結點、一個不留。本題保留一個副本邏輯上更簡單。復雜度分析時間復雜度O(n)其中n為鏈表長度。cur指針從鏈頭走到鏈尾每個結點最多被訪問常數次空間復雜度O(1)。全程僅使用一個輔助指針cur原地修改鏈表不申請任何與輸入規模相關的額外空間。測試用例驗證倉庫為該題編寫了完整的單元測試位于 83. Remove Duplicates from Sorted List_test.go覆蓋了五類典型場景輸入期望輸出覆蓋場景[1, 1, 2][1, 2]題目示例一處重復[1, 1, 2, 2, 3, 3, 3][1, 2, 3]多組重復值連續出現[1, 1, 1, 1, 1, 1, 1, 1][1]全部為相同值壓縮為單結點[][]空鏈表邊界[1][1]單結點邊界測試的構建方式值得留意測試用例沒有直接手寫鏈表而是借助structures包提供的輔助函數完成[]int與鏈表的雙向轉換來自 ListNode.go// List2Ints convert List to []int func List2Ints(head *ListNode) []int { ... } // Ints2List convert []int to List func Ints2List(nums []int) *ListNode { if len(nums) 0 { return nil } l : ListNode{} t : l for _, v : range nums { t.Next ListNode{Val: v} t t.Next } return l.Next }其中Ints2List通過哨兵頭結點l逐個尾插構造鏈表并返回l.NextList2Ints則遍歷鏈表收集數值并內置 100 層深度限制一旦鏈長超過限制會主動panic以攔截可能出現的環狀鏈表避免測試死循環。測試主循環中通過structures.Ints2List(p.one)構造輸入鏈表、調用deleteDuplicates去重后再用structures.List2Ints轉回切片并打印從而直觀核對輸出fmt.Printf(【input】:%v 【output】:%v\n, p, structures.List2Ints(deleteDuplicates(structures.Ints2List(p.one))))在本倉庫中運行測試本倉庫根目錄提供了統一跑測腳本 gotest.sh其內部對所有題目目錄執行全量覆蓋率測試go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...若只想單獨驗證第 83 題的實現與測試可在倉庫根目錄下直接執行go test -v ./leetcode/0083.Remove-Duplicates-from-Sorted-List/倉庫的模塊名為github.com/halfrost/LeetCode-Go見 go.mod題目源碼內部依賴structures公共包且該包已通過replace github.com/halfrost/LeetCode-Go/structures ./structures指向本地目錄因此無需額外聯網拉取私有依賴即可在本地完成編譯與測試。小結第 83 題是對“有序鏈表 相鄰比較”這一組合的經典考查利用鏈表有序的天然性質用單指針一遍掃描、原地改鏈即可完成去重時間復雜度 O(n)、空間復雜度 O(1)。掌握這道題的“跳過重復結點時指針原地不動”這一細節也為后續處理更復雜的鏈表去重題如保留一個不重復版本的變體、刪除全部重復結點等打下基礎。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考 LeetCode 83：刪除排序鏈表中的重復元素 Remove Duplicates from Sorted List（Go 題解）
LeetCode 83刪除排序鏈表中的重復元素 Remove Duplicates from Sorted ListGo 題解【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文圍繞 LeetCode 第 83 題“Remove Duplicates from Sorted List”展開基于本倉庫LeetCode-Go中該題目的完整實現與測試用例從題目語義、解題思路、源碼逐行剖析到復雜度分析系統講解如何在 Go 中刪除有序鏈表中的重復結點。讀完本文你將掌握單指針遍歷有序鏈表去重的核心手法并學會如何在本倉庫中運行該題對應的單元測試進行驗證。題目回顧Given a sorted linked list, delete all duplicates such that each element appear only once.題目要求給定一個已排序的鏈表刪除所有重復的結點使得每個元素只出現一次。注意兩個前提條件——鏈表本身有序、只要求刪除重復值而非保留唯一性計數這決定了題目可以用線性掃描輕松解決。示例 1Input: 1-1-2 Output: 1-2示例 2Input: 1-1-2-3-3 Output: 1-2-3題目大意刪除鏈表中重復的結點以保障每個結點只出現一次。由于鏈表有序所有重復值必然連續相鄰因此只需比較相鄰結點即可完成去重無需借助哈希表等額外數據結構。解題思路本題的核心思路是“按照題意做即可”——維護一個指針cur從頭結點開始遍歷只要cur還有下一個結點就比較cur.Next.Val與cur.Val若相等說明存在重復值直接將cur.Next指向cur.Next.Next跳過重復結點若不相等指針cur正常前移。整個過程只需遍歷一遍鏈表原地修改結點指針不需要新建鏈表也不需要額外的存儲空間。源碼實現與逐行剖析本倉庫中該題的實現位于 83. Remove Duplicates from Sorted List.go完整代碼如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // ListNode define type ListNode structures.ListNode /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func deleteDuplicates(head *ListNode) *ListNode { cur : head if head nil { return nil } if head.Next nil { return head } for cur.Next ! nil { if cur.Next.Val cur.Val { cur.Next cur.Next.Next } else { cur cur.Next } } return head }鏈表結點定義代碼開頭的type ListNode structures.ListNode是一個類型別名直接復用倉庫公共包structures中定義的鏈表結點。真正的結點定義位于 ListNode.go// ListNode 是鏈接節點 // 這個不能復制到*_test.go文件中。會導致Travis失敗 type ListNode struct { Val int Next *ListNode }每個結點包含一個整型值Val和一個指向后繼結點的指針Next與 LeetCode 官方對單鏈表結點的定義完全一致。邊界條件處理cur : head if head nil { return nil } if head.Next nil { return head }函數先處理兩種邊界情況空鏈表head nil直接返回nil僅一個結點head.Next nil不存在重復可能直接返回原鏈表。這兩步保證了后續循環中cur與cur.Next的安全訪問避免空指針解引用。去重主循環for cur.Next ! nil { if cur.Next.Val cur.Val { cur.Next cur.Next.Next } else { cur cur.Next } } return head這是算法的核心值得逐行拆解循環條件cur.Next ! nil確保每次比較都有“當前結點”與“下一結點”這一對相鄰結點當cur.Next.Val cur.Val時說明下一結點是重復值。此時執行cur.Next cur.Next.Next即跳過重復結點把當前結點的后繼指針直接指向下下個結點。注意這里指針cur不移動因為跳過一個結點后新的cur.Next仍可能與cur.Val相同例如1-1-1這種連續多個重復值需要繼續比較當值不相等時cur cur.Next指針正常前進進入下一組相鄰結點。一個關鍵設計點是跳過重復結點時cur保持原地不動。以1-1-2為例cur指向第一個1發現下一個也是1于是cur.Next直接指向2此時循環繼續cur.Next值為2與cur.Val值為1不相等cur前移指向2循環結束輸出1-2。若在跳過結點時貿然前移cur就會漏判連續三個以上重復值的情況如1-1-1。為什么“按題意做”就夠了鏈表已排序這一前提決定了所有相同值在鏈表中是連續成片存在的。因此去重等價于“把連續相同值的片段壓縮為一個結點”只需要一次線性掃描比較相鄰結點即可無需像 0082.Remove-Duplicates-from-Sorted-List-II 那樣額外記錄重復值并整段刪除那道題要求刪除所有重復結點、一個不留。本題保留一個副本邏輯上更簡單。復雜度分析時間復雜度O(n)其中n為鏈表長度。cur指針從鏈頭走到鏈尾每個結點最多被訪問常數次空間復雜度O(1)。全程僅使用一個輔助指針cur原地修改鏈表不申請任何與輸入規模相關的額外空間。測試用例驗證倉庫為該題編寫了完整的單元測試位于 83. Remove Duplicates from Sorted List_test.go覆蓋了五類典型場景輸入期望輸出覆蓋場景[1, 1, 2][1, 2]題目示例一處重復[1, 1, 2, 2, 3, 3, 3][1, 2, 3]多組重復值連續出現[1, 1, 1, 1, 1, 1, 1, 1][1]全部為相同值壓縮為單結點[][]空鏈表邊界[1][1]單結點邊界測試的構建方式值得留意測試用例沒有直接手寫鏈表而是借助structures包提供的輔助函數完成[]int與鏈表的雙向轉換來自 ListNode.go// List2Ints convert List to []int func List2Ints(head *ListNode) []int { ... } // Ints2List convert []int to List func Ints2List(nums []int) *ListNode { if len(nums) 0 { return nil } l : ListNode{} t : l for _, v : range nums { t.Next ListNode{Val: v} t t.Next } return l.Next }其中Ints2List通過哨兵頭結點l逐個尾插構造鏈表并返回l.NextList2Ints則遍歷鏈表收集數值并內置 100 層深度限制一旦鏈長超過限制會主動panic以攔截可能出現的環狀鏈表避免測試死循環。測試主循環中通過structures.Ints2List(p.one)構造輸入鏈表、調用deleteDuplicates去重后再用structures.List2Ints轉回切片并打印從而直觀核對輸出fmt.Printf(【input】:%v 【output】:%v\n, p, structures.List2Ints(deleteDuplicates(structures.Ints2List(p.one))))在本倉庫中運行測試本倉庫根目錄提供了統一跑測腳本 gotest.sh其內部對所有題目目錄執行全量覆蓋率測試go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...若只想單獨驗證第 83 題的實現與測試可在倉庫根目錄下直接執行go test -v ./leetcode/0083.Remove-Duplicates-from-Sorted-List/倉庫的模塊名為github.com/halfrost/LeetCode-Go見 go.mod題目源碼內部依賴structures公共包且該包已通過replace github.com/halfrost/LeetCode-Go/structures ./structures指向本地目錄因此無需額外聯網拉取私有依賴即可在本地完成編譯與測試。小結第 83 題是對“有序鏈表 相鄰比較”這一組合的經典考查利用鏈表有序的天然性質用單指針一遍掃描、原地改鏈即可完成去重時間復雜度 O(n)、空間復雜度 O(1)。掌握這道題的“跳過重復結點時指針原地不動”這一細節也為后續處理更復雜的鏈表去重題如保留一個不重復版本的變體、刪除全部重復結點等打下基礎。【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考