链表
基本技能
链表相关的核心点
- null/nil 异常处理
- dummy node 哑巴节点
- 快慢指针
- 插入一个节点到排序链表
- 从一个链表中移除一个节点
- 翻转链表
- 合并两个链表
- 找到链表的中间节点
常见题型
remove-duplicates-from-sorted-list
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
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 }
remove-duplicates-from-sorted-list-ii
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。
思路：链表头结点可能被删除，所以用 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
reverse-linked-list
反转一个单链表。
思路：用一个 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 }
reverse-linked-list-ii
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
思路：先遍历到 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 }
merge-two-sorted-lists
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：通过 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 }
partition-list
给定一个链表和一个特定值 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
reorder-list
给定一个单链表 L：L→L→…→L__n→L 将其重新排列后变为： L→L__n→L→L__n→L→L__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 }
linked-list-cycle
给定一个链表，判断链表中是否有环。
思路：快慢指针，快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减 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 }
linked-list-cycle-ii
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回
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
palindrome-linked-list
请判断一个链表是否为回文链表。
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 }
copy-list-with-random-pointer
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。
思路：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 哑巴节点
- 快慢指针
- 插入一个节点到排序链表
- 从一个链表中移除一个节点
- 翻转链表
- 合并两个链表
- 找到链表的中间节点