起源

對鏈表而言需要用上上一個節(jié)點(diǎn)的操作對頭結(jié)點(diǎn)就不適合，一個不小心產(chǎn)生許多bug

虛擬節(jié)點(diǎn)~dummy
在鏈表的頭部放入一個哨兵，然后連上head節(jié)點(diǎn)，把head節(jié)點(diǎn)當(dāng)做普通節(jié)點(diǎn)放心使用

ListNode* dummy=new ListNode(-1);dummy->next=head;

最后返回

return dummy->next;

題面

給定一個鏈表，刪除鏈表的倒數(shù)第n個節(jié)點(diǎn)并返回鏈表的頭指針
例如，
給出的鏈表為:1->2->3->4->5, n= 2.
刪除了鏈表的倒數(shù)第n個節(jié)點(diǎn)之后,鏈表變?yōu)?->2->3->5.

上碼

• 快慢指針找到被刪除節(jié)點(diǎn)的前置節(jié)點(diǎn)
• 用哨兵虛擬節(jié)點(diǎn)，解決原生鏈頭操作bug

func removeNthFromEnd( head *ListNode , n int ) *ListNode {dummy := &ListNode{Next: head,}slow,fast := dummy, dummyfor fast != nil && fast.Next != nil{n--if n < 0 {slow = slow.Next}fast = fast.Next}slow.Next = slow.Next.Nextreturn dummy.Next }

交互鏈表節(jié)點(diǎn)

將給定的鏈表中每兩個相鄰的節(jié)點(diǎn)交換一次，返回鏈表的頭指針
要求 只能使用常量級的空間。你不能修改列表中的值，只能修改節(jié)點(diǎn)本身。

例如, 給出1->2->3->4，返回鏈表2->1->4->3

解法

• 引用別名變量左值的修改會導(dǎo)致被引用對象的內(nèi)容發(fā)生改變
• 但步驟一在別名變量被重新賦值后，即產(chǎn)生新的引用地址時，原先被引用鏈接性中斷，只對新來者負(fù)責(zé)
• 區(qū)分左值修改連動性，與左值賦值覆蓋性
• 使用dummy 假面副本別名，本體不動，內(nèi)部修改可追溯
• 先修改指向，占位，后移動指針，補(bǔ)位，賦值意味著重新來過

func swapPairs( head *ListNode ) *ListNode {if head == nil {return nil}dummy := &ListNode{Next: head}for prev,cur := dummy,head; cur != nil && cur.Next != nil; {prev.Next = cur.Nextcur.Next = prev.Next.Nextprev.Next.Next = curprev = curcur = cur.Next}return dummy.Next }

刪除有序鏈表中的重復(fù)元素

只有不相同的情況下，當(dāng)前指針才往后移動

func deleteDuplicates( head *ListNode ) *ListNode {dummy := &ListNode{Next: head}for cur :=dummy;cur!=nil && cur.Next!=nil; {if cur.Next.Val != cur.Val {cur = cur.Next}else{cur.Next = cur.Next.Next}}return dummy.Next }

劃分鏈表

給出一個鏈表和一個值 ，以 為參照將鏈表劃分成兩部分，使所有小于 的節(jié)點(diǎn)都位于大于或等于 的節(jié)點(diǎn)之前。
兩個部分之內(nèi)的節(jié)點(diǎn)之間要保持的原始相對順序。

給出 1→4→3→2→5→2 和 x=3,
返回 1→2→2→4→3→5.

分析

采用雙啞節(jié)點(diǎn)+雙指針，先構(gòu)建中間鏈表，然后將兩個鏈表合并

• 啞節(jié)點(diǎn)指向兩個中間鏈表的頭部
• 指針指向兩個中間鏈表的尾部

func partition( head *ListNode , x int ) *ListNode {dummy := &ListNode{}dummy2 := &ListNode{}p1,p2 := dummy,dummy2for cur:=head; cur!=nil;cur=cur.Next{if cur.Val < x {p1.Next = curp1 = cur}else{p2.Next = curp2 = cur}}p1.Next = dummy2.Nextp2.Next = nilreturn dummy.Next }

• 鏈表序本質(zhì)也是一種有序，只不過是邏輯上指針有序，而非數(shù)組固定物理有序
• 若鏈表重置原地重生成本很高，考慮構(gòu)建新的輔助鏈表，鏈表節(jié)點(diǎn)重建，復(fù)寫

總結(jié)

以上是生活随笔為你收集整理的虚节点dummy的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。