链表

基本技能

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

常见题型

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
func deleteDuplicates(head *ListNode) *ListNode {
current := head
for current != nil {
// 全部删除完再移动到下一个元素
for current.Next != nil && current.Val == current.Next.Val {
current.Next = current.Next.Next
}
current = current.Next
}
return head
}
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现的数字。
思路:链表头结点可能被删除,所以用 dummy node 辅助删除
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return head
}
dummy := &ListNode{Val: 0}
dummy.Next = head
head = dummy
var rmVal int
for head.Next != nil && head.Next.Next != nil {
if head.Next.Val == head.Next.Next.Val {
// 记录已经删除的值,用于后续节点判断
rmVal = head.Next.Val
for head.Next != nil && head.Next.Val == rmVal {
head.Next = head.Next.Next
}
} else {
head = head.Next
}
}
return dummy.Next
}
注意点 • A->B->C 删除 B,A.next = C • 删除用一个 Dummy Node 节点辅助(允许头节点可变) • 访问 X.next 、X.value 一定要保证 X != nil
反转一个单链表。
思路:用一个 prev 节点保存向前指针,temp 保存向后的临时指针
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
// 保存当前head.Next节点,防止重新赋值后被覆盖
// 一轮之后状态:nil<-1 2->3->4
// prev head
temp := head.Next
head.Next = prev
// pre 移动
prev = head
// head 移动
head = temp
}
return prev
}
反转从位置 mn 的链表。请使用一趟扫描完成反转。
思路:先遍历到 m 处,翻转,再拼接后续,注意指针处理
func reverseBetween(head *ListNode, m int, n int) *ListNode {
// 思路:先遍历到m处,翻转,再拼接后续,注意指针处理
// 输入: 1->2->3->4->5->NULL, m = 2, n = 4
if head == nil {
return head
}
// 头部变化所以使用dummy node
dummy := &ListNode{Val: 0}
dummy.Next = head
head = dummy
// 最开始:0->1->2->3->4->5->nil
var pre *ListNode
var i = 0
for i < m {
pre = head
head = head.Next
i++
}
// 遍历之后: 1(pre)->2(head)->3->4->5->NULL
// i = 1
var j = i
var next *ListNode
// 用于中间节点连接
var mid = head
for head != nil && j <= n {
// 第一次循环: 1 nil<-2 3->4->5->nil
temp := head.Next
head.Next = next
next = head
head = temp
j++
}
// 循环需要执行四次
// 循环结束:1 nil<-2<-3<-4 5(head)->nil
pre.Next = next
mid.Next = head
return dummy.Next
}
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路:通过 dummy node 链表,连接各个元素
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{Val: 0}
head := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
head.Next = l1
l1 = l1.Next
} else {
head.Next = l2
l2 = l2.Next
}
head = head.Next
}
// 连接l1 未处理完节点
for l1 != nil {
head.Next = l1
head = head.Next
l1 = l1.Next
}
// 连接l2 未处理完节点
for l2 != nil {
head.Next = l2
head = head.Next
l2 = l2.Next
}
return dummy.Next
}
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
思路:将大于 x 的节点,放到另外一个链表,最后连接这两个链表
func partition(head *ListNode, x int) *ListNode {
// 思路:将大于x的节点,放到另外一个链表,最后连接这两个链表
// check
if head == nil {
return head
}
headDummy := &ListNode{Val: 0}
tailDummy := &ListNode{Val: 0}
tail := tailDummy
headDummy.Next = head
head = headDummy
for head.Next != nil {
if head.Next.Val < x {
head = head.Next
} else {
// 移除<x节点
t := head.Next
head.Next = head.Next.Next
// 放到另外一个链表
tail.Next = t
tail = tail.Next
}
}
// 拼接两个链表
tail.Next = nil
head.Next = tailDummy.Next
return headDummy.Next
}
哑巴节点使用场景
当头节点不确定的时候,使用哑巴节点

sort-list

O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
思路:归并排序,找中点和合并操作
func sortList(head *ListNode) *ListNode {
// 思路:归并排序,找中点和合并操作
return mergeSort(head)
}
func findMiddle(head *ListNode) *ListNode {
// 1->2->3->4->5
slow := head
fast := head.Next
// 快指针先为nil
for fast !=nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{Val: 0}
head := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
head.Next = l1
l1 = l1.Next
} else {
head.Next = l2
l2 = l2.Next
}
head = head.Next
}
// 连接l1 未处理完节点
for l1 != nil {
head.Next = l1
head = head.Next
l1 = l1.Next
}
// 连接l2 未处理完节点
for l2 != nil {
head.Next = l2
head = head.Next
l2 = l2.Next
}
return dummy.Next
}
func mergeSort(head *ListNode) *ListNode {
// 如果只有一个节点 直接就返回这个节点
if head == nil || head.Next == nil{
return head
}
// find middle
middle := findMiddle(head)
// 断开中间节点
tail := middle.Next
middle.Next = nil
left := mergeSort(head)
right := mergeSort(tail)
result := mergeTwoLists(left, right)
return result
}
注意点
  • 快慢指针 判断 fast 及 fast.Next 是否为 nil 值
  • 递归 mergeSort 需要断开中间节点
  • 递归返回条件为 head 为 nil 或者 head.Next 为 nil
给定一个单链表 LLL→…→L__nL 将其重新排列后变为: LL__nLL__nLL__n→…
思路:找到中点断开,翻转后面部分,然后合并前后两个链表
func reorderList(head *ListNode) {
// 思路:找到中点断开,翻转后面部分,然后合并前后两个链表
if head == nil {
return
}
mid := findMiddle(head)
tail := reverseList(mid.Next)
mid.Next = nil
head = mergeTwoLists(head, tail)
}
func findMiddle(head *ListNode) *ListNode {
fast := head.Next
slow := head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{Val: 0}
head := dummy
toggle := true
for l1 != nil && l2 != nil {
// 节点切换
if toggle {
head.Next = l1
l1 = l1.Next
} else {
head.Next = l2
l2 = l2.Next
}
toggle = !toggle
head = head.Next
}
// 连接l1 未处理完节点
for l1 != nil {
head.Next = l1
head = head.Next
l1 = l1.Next
}
// 连接l2 未处理完节点
for l2 != nil {
head.Next = l2
head = head.Next
l2 = l2.Next
}
return dummy.Next
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
// 保存当前head.Next节点,防止重新赋值后被覆盖
// 一轮之后状态:nil<-1 2->3->4
// prev head
temp := head.Next
head.Next = prev
// pre 移动
prev = head
// head 移动
head = temp
}
return prev
}
给定一个链表,判断链表中是否有环。
思路:快慢指针,快慢指针相同则有环,证明:如果有环每走一步快慢指针距离会减 1
func hasCycle(head *ListNode) bool {
// 思路:快慢指针 快慢指针相同则有环,证明:如果有环每走一步快慢指针距离会减1
if head == nil {
return false
}
fast := head.Next
slow := head
for fast != nil && fast.Next != nil {
// 比较指针是否相等(不要使用val比较!)
if fast == slow {
return true
}
fast = fast.Next.Next
slow = slow.Next
}
return false
}
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
思路:快慢指针,快慢相遇之后,慢指针回到头,快慢指针步调一致一起移动,相遇点即为入环点
func detectCycle(head *ListNode) *ListNode {
// 思路:快慢指针,快慢相遇之后,慢指针回到头,快慢指针步调一致一起移动,相遇点即为入环点
if head == nil {
return head
}
fast := head.Next
slow := head
for fast != nil && fast.Next != nil {
if fast == slow {
// 慢指针重新从头开始移动,快指针从第一次相交点下一个节点开始移动
fast = head
slow = slow.Next // 注意
// 比较指针对象(不要比对指针Val值)
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return slow
}
fast = fast.Next.Next
slow = slow.Next
}
return nil
}
坑点
  • 指针比较时直接比较对象,不要用值比较,链表中有可能存在重复值情况
  • 第一次相交后,快指针需要从下一个节点开始和头指针一起匀速移动
另外一种方式是 fast=head,slow=head
func detectCycle(head *ListNode) *ListNode {
// 思路:快慢指针,快慢相遇之后,其中一个指针回到头,快慢指针步调一致一起移动,相遇点即为入环点
// nb+a=2nb+a
if head == nil {
return head
}
fast := head
slow := head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
// 指针重新从头开始移动
fast = head
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return slow
}
}
return nil
}
这两种方式不同点在于,一般用 fast=head.Next 较多,因为这样可以知道中点的上一个节点,可以用来删除等操作。
  • fast 如果初始化为 head.Next 则中点在 slow.Next
  • fast 初始化为 head,则中点在 slow
请判断一个链表是否为回文链表。
func isPalindrome(head *ListNode) bool {
// 1 2 nil
// 1 2 1 nil
// 1 2 2 1 nil
if head==nil{
return true
}
slow:=head
// fast如果初始化为head.Next则中点在slow.Next
// fast初始化为head,则中点在slow
fast:=head.Next
for fast!=nil&&fast.Next!=nil{
fast=fast.Next.Next
slow=slow.Next
}
tail:=reverse(slow.Next)
// 断开两个链表(需要用到中点前一个节点)
slow.Next=nil
for head!=nil&&tail!=nil{
if head.Val!=tail.Val{
return false
}
head=head.Next
tail=tail.Next
}
return true
}
func reverse(head *ListNode)*ListNode{
// 1->2->3
if head==nil{
return head
}
var prev *ListNode
for head!=nil{
t:=head.Next
head.Next=prev
prev=head
head=t
}
return prev
}
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。
思路:1、hash 表存储指针,2、复制节点跟在原节点后面
func copyRandomList(head *Node) *Node {
if head == nil {
return head
}
// 复制节点,紧挨到到后面
// 1->2->3 ==> 1->1'->2->2'->3->3'
cur := head
for cur != nil {
clone := &Node{Val: cur.Val, Next: cur.Next}
temp := cur.Next
cur.Next = clone
cur = temp
}
// 处理random指针
cur = head
for cur != nil {
if cur.Random != nil {
cur.Next.Random = cur.Random.Next
}
cur = cur.Next.Next
}
// 分离两个链表
cur = head
cloneHead := cur.Next
for cur != nil && cur.Next != nil {
temp := cur.Next
cur.Next = cur.Next.Next
cur = temp
}
// 原始链表头:head 1->2->3
// 克隆的链表头:cloneHead 1'->2'->3'
return cloneHead
}

总结

链表必须要掌握的一些点,通过下面练习题,基本大部分的链表类的题目都是手到擒来~
  • null/nil 异常处理
  • dummy node 哑巴节点
  • 快慢指针
  • 插入一个节点到排序链表
  • 从一个链表中移除一个节点
  • 翻转链表
  • 合并两个链表
  • 找到链表的中间节点

练习