微網(wǎng)站怎么用,頭條網(wǎng)站開發(fā),女生seo專員很難嗎為什么,廣告設(shè)計總結(jié)這道題充分利用了鏈表便于刪除節(jié)點的特性#xff0c;以及題目給出的**“已排序”**這個關(guān)鍵前提。1. 解題思路#xff1a;一次遍歷 由于鏈表是已排序的#xff0c;所有重復(fù)的元素在物理位置上一定是相鄰的。 初始化#xff1a;讓一個指針 cur 指向 head。比較與去重#x…這道題充分利用了鏈表便于刪除節(jié)點的特性以及題目給出的**“已排序”**這個關(guān)鍵前提。1. 解題思路一次遍歷由于鏈表是已排序的所有重復(fù)的元素在物理位置上一定是相鄰的。初始化讓一個指針cur指向head。比較與去重比較cur和cur.next的值。如果相等說明遇到了重復(fù)元素。我們只需要讓cur.next cur.next.next相當(dāng)于直接把中間那個重復(fù)的節(jié)點“跳過”了這就是鏈表刪除節(jié)點的高效之處。如果不相等說明當(dāng)前節(jié)點是唯一的將cur向后移動一位。循環(huán)終止當(dāng)cur或cur.next為空時說明遍歷結(jié)束。2. 代碼實現(xiàn) (Python)# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defdeleteDuplicates(self,head:Optional[ListNode])-Optional[ListNode]:# 如果鏈表為空或只有一個節(jié)點直接返回ifnothead:returnhead curhead# 只要當(dāng)前節(jié)點和下一個節(jié)點都存在就繼續(xù)比較whilecurandcur.next:ifcur.valcur.next.val:# 發(fā)現(xiàn)重復(fù)刪除 next 節(jié)點# 直接指向下下個節(jié)點cur.nextcur.next.nextelse:# 不重復(fù)cur 指針后移curcur.nextreturnhead3. 深度解析為什么這題不需要dummy節(jié)點在上一題反轉(zhuǎn)鏈表 II中由于頭節(jié)點可能會被反轉(zhuǎn)/改變我們需要dummy。但在本題中頭節(jié)點永遠不會被刪除。即使后面有和頭節(jié)點值一樣的元素被刪除的也是“后來的”重復(fù)項第一個節(jié)點始終會被保留。既然頭節(jié)點固定我們直接返回head即可不需要額外的虛擬節(jié)點。4. 復(fù)雜度分析時間復(fù)雜度O(N)O(N)O(N)。我們只對鏈表進行了一次完整的線性掃描?？臻g復(fù)雜度O(1)O(1)O(1)。只使用了一個cur指針沒有開辟額外空間。規(guī)則變了只要一個數(shù)字重復(fù)出現(xiàn)過它的所有副本都要被刪除。例如1 - 2 - 2 - 3變成1 - 3中間的2全部消失。1. 核心突破為什么要用dummy節(jié)點在這道題中dummy節(jié)點是必須的。原因在于頭節(jié)點可能會被刪除。例如鏈表是1 - 1 - 2因為1是重復(fù)的它必須被刪掉。如果沒有dummy你很難處理“誰來當(dāng)新的頭”這個問題。有了dummy我們只需要最后返回dummy.next。2. 解題思路三步走設(shè)置哨兵創(chuàng)建dummy指向head令pre指向dummy。pre的作用是始終指向“確定不重復(fù)的最后一個節(jié)點”。尋找重復(fù)區(qū)間讓cur指向pre.next。如果發(fā)現(xiàn)cur.val cur.next.val說明我們進入了一個重復(fù)區(qū)域。批量跳過利用一個while循環(huán)讓cur一直向后移動直到跳過所有值相同的節(jié)點。最后讓pre.next cur.next直接把這一整段重復(fù)的“一刀切掉”。3. 代碼實現(xiàn) (Python)classSolution:defdeleteDuplicates(self,head:Optional[ListNode])-Optional[ListNode]:# 1. 只要頭節(jié)點可能被刪就請出 dummydummyListNode(0,head)predummywhilepre.nextandpre.next.next:# 檢查接下來兩個節(jié)點的值是否相同ifpre.next.valpre.next.next.val:# 記錄這個重復(fù)的值xpre.next.val# 只要接下來的節(jié)點值等于 x就不斷跳過currpre.nextwhilecurrandcurr.valx:currcurr.next# 將 pre 的 next 指向第一個不等于 x 的節(jié)點pre.nextcurrelse:# 如果不重復(fù)pre 才可以放心前進一步prepre.nextreturndummy.next4. 關(guān)鍵邏輯點撥為什么pre不直接移動在發(fā)現(xiàn)重復(fù)時pre.next curr之后pre不能立即后移。因為新接上的這個curr節(jié)點可能又是另一組重復(fù)數(shù)字的開始。必須在下一輪循環(huán)中再次檢查。對比 83 題83 題保留重復(fù)項中的一個。所以發(fā)現(xiàn)重復(fù)時cur.next cur.next.nextcur本身不動。82 題一個不留。所以需要一個內(nèi)層循環(huán)把所有val相同的都走完然后讓pre跨越式連接。5. 復(fù)雜度分析時間復(fù)雜度O(N)O(N)O(N)。雖然有嵌套循環(huán)但每個節(jié)點最多只被訪問兩次一次由curr掃描一次作為pre.next依然是線性時間。空間復(fù)雜度O(1)O(1)O(1)。通過這兩道題83 和 82的對比感覺到dummy節(jié)點在處理“頭節(jié)點可能消失”的問題時是多么好用了whilecurrandcurr.valx:這行代碼體現(xiàn)了 Python 中的兩個重要概念短路邏輯Short-circuiting和循環(huán)過濾。1. 拆解這行代碼這行代碼的作用是“只要當(dāng)前節(jié)點存在并且它的值還是我們要找的重復(fù)值就一直往后走?！眞hile: 開啟一個循環(huán)。curr: 檢查curr是否為None。如果curr已經(jīng)走到了鏈表的末尾即空指針這個條件就是False。and: 邏輯與操作。curr.val x: 檢查當(dāng)前節(jié)點的值是否等于我們要刪除的那個重復(fù)值x。2. 為什么要加curr and ...防止報錯這是這段代碼最關(guān)鍵的地方。在鏈表操作中我們經(jīng)常會遇到空指針異常。如果鏈表的結(jié)尾正好是一串重復(fù)數(shù)字比如1 - 2 - 2 - None第一個2curr存在val是 2進入循環(huán)。第二個2curr存在val是 2進入循環(huán)。關(guān)鍵點此時curr移動到了None。如果沒有curr and代碼會直接執(zhí)行None.val 2。這時候程序會崩潰拋出AttributeError: NoneType object has no attribute val。Python 的短路原則在A and B中如果A已經(jīng)是False了Python 根本不會去看B是什么。所以先判斷curr是否存在可以安全地保護后面的.val操作不報錯。3. 這種語法的目的批量跳過在第 82 題中我們要“一個不留”地刪除重復(fù)項。假設(shè)鏈表是pre - 2 - 2 - 2 - 3此時x 2。curr最初指向第一個2。while curr and curr.val x:會讓curr像跳格子一樣跳過第一個2跳過第二個2跳過第三個2最后curr停在了3的位置。退出循環(huán)后我們執(zhí)行pre.next curr。效果就是pre的下一跳直接變成了3中間那串2被整體切除了?？偨Y(jié)這是一種非常經(jīng)典的**“過濾重復(fù)區(qū)間”**的寫法用x記住那個“壞掉”的值。用while配合指針移動把所有等于x的連續(xù)節(jié)點全部走完。利用and的短路特性保證代碼的健壯性魯棒性。這種“先檢查指針是否為空再訪問指針成員”的習(xí)慣在寫任何鏈表或樹Tree的代碼時都是必須具備的。