linked_list.md

链表

基本技能

链表相关的核心点

• null/nil 异常处理
• dummy node 哑巴节点
• 快慢指针
• 插入一个节点到排序链表
• 从一个链表中移除一个节点
• 翻转链表
• 合并两个链表
• 找到链表的中间节点

常见题型

remove-duplicates-from-sorted-list

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

funcdeleteDuplicates(head*ListNode) *ListNode {
current:=headforcurrent!=nil {
// 全部删除完再移动到下一个元素forcurrent.Next!=nil&&current.Val==current.Next.Val {
current.Next=current.Next.Next
}
current=current.Next
}
returnhead
}

remove-duplicates-from-sorted-list-ii

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。

思路：链表头结点可能被删除，所以用 dummy node 辅助删除

funcdeleteDuplicates(head*ListNode) *ListNode {
ifhead==nil {
returnhead
}
dummy:=&ListNode{Val: 0}
dummy.Next=headhead=dummyvarrmValintforhead.Next!=nil&&head.Next.Next!=nil {
ifhead.Next.Val==head.Next.Next.Val {
// 记录已经删除的值，用于后续节点判断rmVal=head.Next.Valforhead.Next!=nil&&head.Next.Val==rmVal {
head.Next=head.Next.Next
}
} else {
head=head.Next
}
}
returndummy.Next
}

注意点 • A->B->C 删除 B，A.next = C • 删除用一个 Dummy Node 节点辅助（允许头节点可变） • 访问 X.next 、X.value 一定要保证 X != nil

reverse-linked-list

反转一个单链表。

思路：用一个 prev 节点保存向前指针，temp 保存向后的临时指针

funcreverseList(head*ListNode) *ListNode {
varprev*ListNodeforhead!=nil {
// 保存当前head.Next节点，防止重新赋值后被覆盖// 一轮之后状态：nil<-1 2->3->4// prev headtemp:=head.Nexthead.Next=prev// pre 移动prev=head// head 移动head=temp
}
returnprev
}

reverse-linked-list-ii

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

思路：先遍历到 m 处，翻转，再拼接后续，注意指针处理

funcreverseBetween(head*ListNode, mint, nint) *ListNode {
// 思路：先遍历到m处，翻转，再拼接后续，注意指针处理// 输入: 1->2->3->4->5->NULL, m = 2, n = 4ifhead==nil {
returnhead
}
// 头部变化所以使用dummy nodedummy:=&ListNode{Val: 0}
dummy.Next=headhead=dummy// 最开始：0->1->2->3->4->5->nilvarpre*ListNodevari=0fori<m {
pre=headhead=head.Nexti++
}
// 遍历之后： 1(pre)->2(head)->3->4->5->NULL// i = 1varj=ivarnext*ListNode// 用于中间节点连接varmid=headforhead!=nil&&j<=n {
// 第一次循环： 1 nil<-2 3->4->5->niltemp:=head.Nexthead.Next=nextnext=headhead=tempj++
}
// 循环需要执行四次// 循环结束：1 nil<-2<-3<-4 5(head)->nilpre.Next=nextmid.Next=headreturndummy.Next
}

merge-two-sorted-lists

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：通过 dummy node 链表，连接各个元素

funcmergeTwoLists(l1*ListNode, l2*ListNode) *ListNode {
dummy:=&ListNode{Val: 0}
head:=dummyforl1!=nil&&l2!=nil {
ifl1.Val<l2.Val {
head.Next=l1l1=l1.Next
} else {
head.Next=l2l2=l2.Next
}
head=head.Next
}
// 连接l1 未处理完节点forl1!=nil {
head.Next=l1head=head.Nextl1=l1.Next
}
// 连接l2 未处理完节点forl2!=nil {
head.Next=l2head=head.Nextl2=l2.Next
}
returndummy.Next
}

partition-list

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

思路：将大于 x 的节点，放到另外一个链表，最后连接这两个链表

funcpartition(head*ListNode, xint) *ListNode {
// 思路：将大于x的节点，放到另外一个链表，最后连接这两个链表// checkifhead==nil {
returnhead
}
headDummy:=&ListNode{Val: 0}
tailDummy:=&ListNode{Val: 0}
tail:=tailDummyheadDummy.Next=headhead=headDummyforhead.Next!=nil {
ifhead.Next.Val<x {
head=head.Next
} else {
// 移除<x节点t:=head.Nexthead.Next=head.Next.Next// 放到另外一个链表tail.Next=ttail=tail.Next
}
}
// 拼接两个链表tail.Next=nilhead.Next=tailDummy.NextreturnheadDummy.Next
}

哑巴节点使用场景

当头节点不确定的时候，使用哑巴节点

sort-list

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

思路：归并排序，找中点和合并操作

funcsortList(head*ListNode) *ListNode {
// 思路：归并排序，找中点和合并操作returnmergeSort(head)
}
funcfindMiddle(head*ListNode) *ListNode {
// 1->2->3->4->5slow:=headfast:=head.Next// 快指针先为nilforfast!=nil&&fast.Next!=nil {
fast=fast.Next.Nextslow=slow.Next
}
returnslow
}
funcmergeTwoLists(l1*ListNode, l2*ListNode) *ListNode {
dummy:=&ListNode{Val: 0}
head:=dummyforl1!=nil&&l2!=nil {
ifl1.Val<l2.Val {
head.Next=l1l1=l1.Next
} else {
head.Next=l2l2=l2.Next
}
head=head.Next
}
// 连接l1 未处理完节点forl1!=nil {
head.Next=l1head=head.Nextl1=l1.Next
}
// 连接l2 未处理完节点forl2!=nil {
head.Next=l2head=head.Nextl2=l2.Next
}
returndummy.Next
}
funcmergeSort(head*ListNode) *ListNode {
// 如果只有一个节点 直接就返回这个节点ifhead==nil||head.Next==nil{
returnhead
}
// find middlemiddle:=findMiddle(head)
// 断开中间节点tail:=middle.Nextmiddle.Next=nilleft:=mergeSort(head)
right:=mergeSort(tail)
result:=mergeTwoLists(left, right)
returnresult
}

注意点

• 快慢指针 判断 fast 及 fast.Next 是否为 nil 值
• 递归 mergeSort 需要断开中间节点
• 递归返回条件为 head 为 nil 或者 head.Next 为 nil

reorder-list

给定一个单链表 L：L→L→…→L__n→L 将其重新排列后变为： L→L__n→L→L__n→L→L__n→…

思路：找到中点断开，翻转后面部分，然后合并前后两个链表

funcreorderList(head*ListNode) {
// 思路：找到中点断开，翻转后面部分，然后合并前后两个链表ifhead==nil {
return
}
mid:=findMiddle(head)
tail:=reverseList(mid.Next)
mid.Next=nilhead=mergeTwoLists(head, tail)
}
funcfindMiddle(head*ListNode) *ListNode {
fast:=head.Nextslow:=headforfast!=nil&&fast.Next!=nil {
fast=fast.Next.Nextslow=slow.Next
}
returnslow
}
funcmergeTwoLists(l1*ListNode, l2*ListNode) *ListNode {
dummy:=&ListNode{Val: 0}
head:=dummytoggle:=trueforl1!=nil&&l2!=nil {
// 节点切换iftoggle {
head.Next=l1l1=l1.Next
} else {
head.Next=l2l2=l2.Next
}
toggle=!togglehead=head.Next
}
// 连接l1 未处理完节点forl1!=nil {
head.Next=l1head=head.Nextl1=l1.Next
}
// 连接l2 未处理完节点forl2!=nil {
head.Next=l2head=head.Nextl2=l2.Next
}
returndummy.Next
}
funcreverseList(head*ListNode) *ListNode {
varprev*ListNodeforhead!=nil {
// 保存当前head.Next节点，防止重新赋值后被覆盖// 一轮之后状态：nil<-1 2->3->4// prev headtemp:=head.Nexthead.Next=prev// pre 移动prev=head// head 移动head=temp
}
returnprev
}

linked-list-cycle

给定一个链表，判断链表中是否有环。

思路：快慢指针，快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减 1

funchasCycle(head*ListNode) bool {
// 思路：快慢指针 快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减1ifhead==nil {
returnfalse
}
fast:=head.Nextslow:=headforfast!=nil&&fast.Next!=nil {
// 比较指针是否相等（不要使用val比较！）iffast==slow {
returntrue
}
fast=fast.Next.Nextslow=slow.Next
}
returnfalse
}

linked-list-cycle-ii

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，相遇点即为入环点

funcdetectCycle(head*ListNode) *ListNode {
// 思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，相遇点即为入环点ifhead==nil {
returnhead
}
fast:=head.Nextslow:=headforfast!=nil&&fast.Next!=nil {
iffast==slow {
// 慢指针重新从头开始移动，快指针从第一次相交点下一个节点开始移动fast=headslow=slow.Next// 注意// 比较指针对象（不要比对指针Val值）forfast!=slow {
fast=fast.Nextslow=slow.Next
}
returnslow
}
fast=fast.Next.Nextslow=slow.Next
}
returnnil
}

坑点

• 指针比较时直接比较对象，不要用值比较，链表中有可能存在重复值情况
• 第一次相交后，快指针需要从下一个节点开始和头指针一起匀速移动

另外一种方式是 fast=head,slow=head

funcdetectCycle(head*ListNode) *ListNode {
// 思路：快慢指针，快慢相遇之后，其中一个指针回到头，快慢指针步调一致一起移动，相遇点即为入环点// nb+a=2nb+aifhead==nil {
returnhead
}
fast:=headslow:=headforfast!=nil&&fast.Next!=nil {
fast=fast.Next.Nextslow=slow.Nextiffast==slow {
// 指针重新从头开始移动fast=headforfast!=slow {
fast=fast.Nextslow=slow.Next
}
returnslow
}
}
returnnil
}

这两种方式不同点在于，一般用 fast=head.Next 较多，因为这样可以知道中点的上一个节点，可以用来删除等操作。

• fast 如果初始化为 head.Next 则中点在 slow.Next
• fast 初始化为 head,则中点在 slow

palindrome-linked-list

请判断一个链表是否为回文链表。

funcisPalindrome(head*ListNode) bool {
// 1 2 nil// 1 2 1 nil// 1 2 2 1 nilifhead==nil{
returntrue
}
slow:=head// fast如果初始化为head.Next则中点在slow.Next// fast初始化为head,则中点在slowfast:=head.Nextforfast!=nil&&fast.Next!=nil{
fast=fast.Next.Nextslow=slow.Next
}
tail:=reverse(slow.Next)
// 断开两个链表(需要用到中点前一个节点)slow.Next=nilforhead!=nil&&tail!=nil{
ifhead.Val!=tail.Val{
returnfalse
}
head=head.Nexttail=tail.Next
}
returntrue
}
funcreverse(head*ListNode)*ListNode{
// 1->2->3ifhead==nil{
returnhead
}
varprev*ListNodeforhead!=nil{
t:=head.Nexthead.Next=prevprev=headhead=t
}
returnprev
}

copy-list-with-random-pointer

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。

思路：1、hash 表存储指针，2、复制节点跟在原节点后面

funccopyRandomList(head*Node) *Node {
ifhead==nil {
returnhead
}
// 复制节点，紧挨到到后面// 1->2->3 ==> 1->1'->2->2'->3->3'cur:=headforcur!=nil {
clone:=&Node{Val: cur.Val, Next: cur.Next}
temp:=cur.Nextcur.Next=clonecur=temp
}
// 处理random指针cur=headforcur!=nil {
ifcur.Random!=nil {
cur.Next.Random=cur.Random.Next
}
cur=cur.Next.Next
}
// 分离两个链表cur=headcloneHead:=cur.Nextforcur!=nil&&cur.Next!=nil {
temp:=cur.Nextcur.Next=cur.Next.Nextcur=temp
}
// 原始链表头：head 1->2->3// 克隆的链表头：cloneHead 1'->2'->3'returncloneHead
}

总结

链表必须要掌握的一些点，通过下面练习题，基本大部分的链表类的题目都是手到擒来~

• null/nil 异常处理
• dummy node 哑巴节点
• 快慢指针
• 插入一个节点到排序链表
• 从一个链表中移除一个节点
• 翻转链表
• 合并两个链表
• 找到链表的中间节点

练习

• remove-duplicates-from-sorted-list
• remove-duplicates-from-sorted-list-ii
• reverse-linked-list
• reverse-linked-list-ii
• merge-two-sorted-lists
• partition-list
• sort-list
• reorder-list
• linked-list-cycle
• linked-list-cycle-ii
• palindrome-linked-list
• copy-list-with-random-pointer