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