1. 链表简介

链表（Linked List）是最简单的线性的、动态数据结构。理解它是理解树结构、图结构的基础。
区别于数组，链表中的元素不是存储在内存中连续的一片区域，链表中的数据存储在每一个称之为「结点」复合区域里，在每一个结点除了存储数据以外，还保存了到下一个节点的指针（Pointer）。
链表 - 图1
由于不必按顺序存储，链表在插入数据的时候可以达到 O(1)O(1) 的复杂度，但是查找一个节点或者访问特定编号的节点则需要 O(n)O(n) 的时间。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（links）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。
链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
链表通常可以衍生出循环链表，静态链表，双链表等。对于链表使用，灵活使用虚拟头结点可以简化问题。

2. 链表架构

双向链表中向头部、尾部添加元素，删除元素，遍历元素。

  1. //创建双向链表
  2. type Node struct {
  3.     Val int
  4.     Next *Node
  5.     Pre  *Node
  6. }
  8. head := &Node{0,nil,nil}
  10. node1 := &Node{1,nil,nil}
  12. node2 := &Node{2,nil,nil}
  14. node3 := &Node{3,nil,nil}
  16. node4 := &Node{4,nil,nil}
  18. node5 := &Node{5,nil,nil}
  20. //在链表的尾部追加元素
  21. node.Next = node1
  22. node1.Pre = node
  23. node1.Next = node2
  24. node2.Pre = node1
  25. node2.Next = node3
  26. node3.Pre = node2
  27. node3.Next = node4
  28. node4.Pre = node3
  29. node4.Next = node5
  30. node5.Pre = node4
  32. //删除node4
  33. node4.Pre.Next = node4.Next
  34. node4.Next.Pre = node.Pre
  36. //在头部添加元素
  37. node0 := &Node{-1,nil,nil} //创建节点
  38. node := head                 //一定要copy节点，不然有问题
  39. node0.Next = node
  40. node.Pre = node0
  41. head = node0
  44. //遍历元素
  45. cur := node
  46. for cur!= nil {
  47.     fmt.Println(cur.Val)
  48. }

3. 删除节点必须 掌握

237. 删除链表中的节点 简单

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

示例 3：
输入：head = [1,2,3,4], node = 3
输出：[1,2,4]

示例 4：
输入：head = [0,1], node = 0
输出：[1]

示例 5：
输入：head = [-3,5,-99], node = -3
输出：[5,-99]

提示：
链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是唯一的
需要删除的节点 node 是 链表中的一个有效节点 ，且 不是末尾节点

题解概要：

  1. 本题没有给头节点，所有无法知道5的上一节点。
  2. 因此，将5节点的值改为1，指针直接指向9节点。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. import "fmt"
  9. func deleteNode(node *ListNode) {
  11.     node.Val = node.Next.Val
  12.     node.Next = node.Next.Next    
  14. }

剑指 Offer 18. 删除链表的节点 简单

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：
题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

题解概要：

  1. 需要特殊处理头部节点
  2. 使用快慢指针，将目标节点的前一节点指向目标节点后一节点。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func deleteNode(head *ListNode, val int) *ListNode {
  10.     if head == nil{
  11.         return head
  12.     }
  14.     if head.Val == val {
  15.         return head.Next
  16.     }
  18.     pre,cur := head,head  //快慢指针
  19.     for cur != nil && cur.Val != val{
  20.         pre,cur = cur,cur.Next
  21.     }
  23.     if cur != nil{
  24.         pre.Next = cur.Next
  25.     }
  27.     return head
  28. }

203. 移除链表元素 简单

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。

示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

题解概要：

  1. 需要虚拟头部节点。

  2. 使用快慢指针遍历链表。

    1. 若出现指定元素，则删除节点。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func removeElements(head *ListNode, val int) *ListNode {
  10.     temp := &ListNode{} //创建虚拟头节点
  11.     temp.Next = head
  12.     pre,cur := temp,head
  13.     for cur != nil{
  14.         //当出现指定节点时，删除该节点，此时慢指针不需要移动。
  15.         if cur.Val == val{
  16.             pre.Next = cur.Next
  17.         }else{
  18.             pre = cur
  19.         }
  20.         cur = cur.Next
  21.     }
  22.     return temp.Next
  23. }

剑指 Offer 22. 链表中倒数第k个节点 简单

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例 1：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

题解概要：

解法一：
使用map记录索引和指针。最后根据索引返回指针即可。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func getKthFromEnd(head *ListNode, k int) *ListNode {
  10.     sMap := make(map[int]*ListNode)
  11.     n := 0
  12.     node := head
  14.     for node != nil{
  15.         n += 1
  16.         sMap[n] = node.Next  
  17.         node = node.Next
  18.     }
  20.     if n-k == 0{
  21.         return head
  22.     }
  24.     return sMap[n-k]
  25. }

解法二：
使用快慢指针，快指针先走k步。同时，快指针和慢指针每一次各走一步，直至快指针走完。此时慢指针节点为所求节点。

  1. import "fmt"
  2. func getKthFromEnd(head *ListNode, k int) *ListNode {
  4.     fast,slow := head,head
  5.     i := 0
  6.     for i < k-1 {        //赋值时已经走了一步，所以为k-1
  8.         fast = fast.Next
  10.         i += 1
  12.     }
  14.     for fast.Next != nil{
  16.         fast = fast.Next
  17.         slow = slow.Next
  19.     }
  21.     return slow
  23. }

19. 删除链表的倒数第 N 个结点 中等

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

题解概要：

  1. 本题需找到两个关键节点：倒数第n个节点的前一节点与后一节点。
  2. 通过链表中倒数第k个节点这道题，我们知道，可以用快慢指针来拿到倒数第n个节点。快指针先遍历n次，慢指针再遍历，直到快指针遍历到链表尾部。此时慢指针恰好是倒数第n个节点。
  3. 因为移除节点有可能在头部，所以要构建虚拟头节点。（这样就无需单独处理特殊情况）
  4. 无法确定边界条件时，可在纸上画出节点移动过程，或运行代码打印边界值。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func removeNthFromEnd(head *ListNode, n int) *ListNode {
  9.     dummry := &ListNode{}
  10.     dummry.Next = head
  11.     slow,fast := dummry,dummry
  12.     for i := 0;i < n;i ++{
  13.         fast = fast.Next
  14.     }
  16.     for fast.Next != nil{
  17.         slow = slow.Next
  18.         fast = fast.Next
  19.     }
  20.     slow.Next = slow.Next.Next
  21.     return dummry.Next
  22. }

面试题 02.01. 移除重复节点 简单

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]

示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]

提示：
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

题解概要：

  1. 使用散列表记录节点值是否已出现。
  2. 使用快慢指针遍历链表。

代码：

  1. func removeDuplicateNodes(head *ListNode) *ListNode {
  3.     var node ListNode
  4.     pre := &node
  5.     cur := head
  7.     arr := [20001]int{}
  9.     for cur != nil{
  11.         if arr[cur.Val] != 0{    //若节点已出现，则快指针右移
  12.             cur = cur.Next
  13.         }else{
  14.             arr[cur.Val] += 1    //若节点未出现，则更新节点出现次数
  15.             pre.Next = cur        //将慢指针指向快指针当前节点
  16.             cur = cur.Next        //快指针右移
  17.             pre = pre.Next        //慢指针右移
  18.         }
  19.     }
  21.     pre.Next = nil                //边界值处理
  23.     last := &node                //虚拟头节点
  25.     return last.Next
  27. }

82. 删除排序链表中的重复元素 II 中等

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]

提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

题解概要：

  1. https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/fu-xue-ming-zhu-di-gui-die-dai-yi-pian-t-wy0h/

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func deleteDuplicates(head *ListNode) *ListNode {
  10.     dummry := &ListNode{}
  11.     dummry.Next = head
  12.     pre,cur := dummry,head
  13.     //一次遍历，模拟删除的过程！
  14.     for cur != nil{
  15.         for cur.Next != nil && cur.Val == cur.Next.Val{
  16.             cur = cur.Next
  17.         }
  18.         if pre.Next == cur{
  19.             pre = cur
  20.         }else{
  21.             pre.Next = cur.Next
  22.         }
  23.         cur = cur.Next
  24.     }
  25.     return dummry.Next
  26. }

4. 翻转链表必须 掌握

206. 反转链表 简单

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题解概要：

  1. 使用快慢指针，修改指针的指向即可。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func reverseList(head *ListNode) *ListNode {
  10.     var pre *ListNode = nil        //创建空节点
  11.     var cur *ListNode = head
  13.     for cur != nil{
  15.         next := cur.Next
  16.         cur.Next = pre
  17.         pre = cur
  18.         cur = next
  20.     }
  21.     return pre
  22. }

92. 反转链表 II 中等

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
链表 - 图2

示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]

提示：
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

题解概要：

  1. 找到4个关键节点，然后将中间部分链表切断，进行翻转，最后再接回。

代码：

  1. func reverseBetween(head *ListNode, left int, right int) *ListNode {
  2.     temp := &ListNode{}
  3.     temp.Next = head
  4.     pre := temp
  5.     //先移动left-1次,找到left的前一个节点
  6.     for i := 0;i < left-1;i++{
  7.         pre = pre.Next
  8.     }
  9.     preNode := pre
  10.     //再移动right-left+1次，找到right节点。
  11.     for i := 0;i < right-left+1;i++{
  12.         pre = pre.Next
  13.     }
  14.     rightNode := pre   //right节点
  15.     leftNode := preNode.Next //left节点
  16.     curNode := rightNode.Next//right节点的下一节点。
  17.     //切断链表
  18.     rightNode.Next = nil
  19.     preNode.Next = nil
  20.     //翻转left到right这一段链表
  21.     reverse(leftNode)
  22.     //将翻转后的链表接回
  23.     preNode.Next = rightNode
  24.     leftNode.Next = curNode
  25.     return temp.Next
  26. }
  28. func reverse(head *ListNode){
  29.     temp := &ListNode{}
  30.     temp.Next = head
  31.     pre,cur := temp,head
  32.     for cur != nil{
  33.         node := cur.Next
  34.         cur.Next = pre
  35.         pre = cur
  36.         cur = node
  37.     }
  38. }

61. 旋转链表 中等

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]
链表 - 图3

提示：

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

题解概要：

  1. 先找到尾节点和链表的长度。再找到n-k个节点，再进行切断重连。

代码：

  1. func rotateRight(head *ListNode, k int) *ListNode {
  2.     if head == nil || head.Next == nil || k == 0{
  3.         return head
  4.     } //特殊情况的处理
  6.     n := 1
  7.     tail := head
  8.     //找到尾节点，并且找到链表的长度
  9.     for tail.Next != nil{
  10.         n ++
  11.         tail = tail.Next
  12.     }
  13.     k %= n
  14.     //是否需要旋转
  15.     if k == 0{
  16.         return head
  17.     }
  18.     //找到前n-k个节点
  19.     pre := head
  20.     for i := 0;i < n-k-1;i++{
  21.         pre = pre.Next
  22.     }
  23.     //切断链表并重新连接链表。
  24.     newHead := pre.Next
  25.     pre.Next = nil
  26.     tail.Next = head
  28.     return newHead
  29. }

24. 两两交换链表中的节点 中等

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：
链表 - 图4
输入：head = [1,2,3,4] 输出：[2,1,4,3]

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

题解概要：

  1. 和第25题是一模一样的，只是k是2而已。

代码：

  1. func swapPairs(head *ListNode) *ListNode {
  2.     //特殊情况的判断
  3.     if head == nil || head.Next == nil{
  4.         return head
  5.     }
  6.     tail := head
  7.     for i := 0;i < 2;i++{
  8.         if tail == nil{
  9.             return head
  10.         }
  11.         tail = tail.Next
  12.     }
  13.     //翻转开始
  14.     newHead := reverse(head,tail)
  15.     //进行下次递归翻转
  16.     head.Next = swapPairs(tail)
  17.     return newHead
  18. }
  21. func reverse(head *ListNode,tail *ListNode)*ListNode{
  22.     var pre *ListNode = nil        //创建空节点
  23.     var cur *ListNode = head
  24.     for cur != tail{
  25.         next := cur.Next
  26.         cur.Next = pre
  27.         pre = cur
  28.         cur = next
  29.     }
  30.     return pre
  31. }

25. K 个一组翻转链表 困难

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

示例 3：
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]

示例 4：
输入：head = [1], k = 1
输出：[1]

提示：
列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz

题解概要：

1、找到待翻转的k个节点（注意：若剩余数量小于 k 的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。
2、对其进行翻转。并返回翻转后的头结点（注意：翻转为左闭又开区间，所以本轮操作的尾结点其实就是下一轮操作的头结点）。
3、对下一轮 k 个节点也进行翻转操作。
4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的k的节点连接起来。

链表 - 图5

代码：

  1. func reverseKGroup(head *ListNode, k int) *ListNode {
  2.     //特殊情况的判断
  3.     if head == nil || head.Next == nil || k <= 1{
  4.         return head
  5.     }
  6.     tail := head
  7.     for i := 0;i < k;i++{
  8.         if tail == nil{
  9.             return head
  10.         }
  11.         tail = tail.Next
  12.     }
  13.     //翻转开始
  14.     newHead := reverse(head,tail)
  15.     //进行下次递归翻转
  16.     head.Next = reverseKGroup(tail,k)
  17.     return newHead
  18. }
  20. func reverse(head *ListNode,tail *ListNode)*ListNode{
  21.     var pre *ListNode = nil        //创建空节点
  22.     var cur *ListNode = head
  23.     for cur != tail{
  24.         next := cur.Next
  25.         cur.Next = pre
  26.         pre = cur
  27.         cur = next
  28.     }
  29.     return pre
  30. }

5. 合并链表必须 掌握

剑指 Offer 25. 合并两个排序的链表 简单

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

题解概要：

  1. 递归调用。也可以使用迭代法，在这里使用递归是更好的选择，优雅！
  2. 迭代法，需要创建新的链表，并需要处理很多边界问题。

递归法

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
  9.     if list1 == nil{
  10.         return list2
  11.     }
  12.     if list2 == nil{
  13.         return list1
  14.     }
  15.     if list1.Val < list2.Val{
  16.         list1.Next = mergeTwoLists(list1.Next,list2)
  17.         return list1
  18.     }else{
  19.         list2.Next = mergeTwoLists(list2.Next,list1)
  20.         return list2
  21.     }
  22. }

迭代法

  1. func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  3.     var cur ListNode
  5.     head := &cur               //初始化新链表(这里无法使用 var cur *ListNode初始化)
  7.     current := head            //用current进行新链表赋值
  9.     for l1 != nil && l2 != nil{
  10.         if l1.Val <= l2.Val{    //比较节点大小
  11.             current.Next = l1
  12.             l1 = l1.Next
  13.         }else{
  14.             current.Next = l2
  15.             l2 = l2.Next
  16.         }
  17.         current = current.Next  //新链表移动到尾部
  18.     } 
  20.     if l1 != nil{              //链接剩余部分
  21.         current.Next = l1
  22.     }else if l2 != nil {
  23.         current.Next = l2
  24.     }
  26.     return head.Next         //head是我们虚拟的头节点，有效头节点是head.Next。
  28. }

1669. 合并两个链表 中等

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：
链表 - 图6
请你返回结果链表的头指针。

示例 1：
输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

示例 2：
输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。

提示：
3 <= list1.length <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104

题解概要：

  1. 需找到3个节点，a的前一节点，b的后一节点与list2最后一个节点。
  2. 将a的前一节点指向list2，list2的最后一个节点指向b的后一节点。
  3. 为了方便操作，最好是构建虚拟节点。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
  9.     //创建虚拟节点
  10.     dummry := &ListNode{}
  11.     dummry.Next = list1
  12.     tail1 := dummry          //第一段的尾节点
  13.     tail3 := list1           //第三段的尾节点
  14.     for i := 0;i < a;i++{
  15.         tail1 = tail1.Next
  16.     }
  17.     for i := 0;i <= b;i++{
  18.         tail3 = tail3.Next
  19.     }
  21.     //找到list2的尾部节点
  22.     tail2 := list2
  23.     for tail2.Next != nil{
  24.         tail2 = tail2.Next
  25.     }
  26.     tail1.Next = list2
  27.     tail2.Next = tail3
  28.     return list1
  29. }

23. 合并K个升序链表 困难

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：
输入：lists = []
输出：[]

示例 3：
输入：lists = [[]]
输出：[]

提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

题解概要：

  1. 分而治之，和归并排序的思路是一样的，两个合并链表，使之有序，最后的时间复杂度是nlogk。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func mergeKLists(lists []*ListNode) *ListNode {
  9.     //判断是否为空
  10.     if len(lists) == 0{
  11.         return nil
  12.     }
  13.     return help(lists,0,len(lists)-1)
  14. }
  16. func help(lists []*ListNode,start int,end int)*ListNode{
  17.     if start == end{
  18.         return lists[start]
  19.     }
  20.     mid := start + (end-start) / 2
  21.     l1 := help(lists,start,mid)
  22.     l2 := help(lists,mid+1,end)
  23.     return merge(l1,l2)
  24. }
  26. func merge(l1 *ListNode,l2 *ListNode)*ListNode{
  27.     if l1 == nil{
  28.         return l2
  29.     }
  30.     if l2 == nil{
  31.         return l1
  32.     }
  33.     if l1.Val < l2.Val{
  34.         l1.Next = merge(l1.Next,l2)
  35.         return l1
  36.     }else{
  37.         l2.Next = merge(l2.Next,l1)
  38.         return l2
  39.     }
  41. }

148. 排序链表 中等

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

题解概要：

  1. 分而治之，和归并排序的思路是一样的，两个合并链表，使之有序，最后的时间复杂度是nlogk。但要注意找到中间的mid之后要将链表切开！

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func sortList(head *ListNode) *ListNode {
  9.     if head == nil || head.Next == nil{
  10.         return head
  11.     }
  12.     lists := []*ListNode{}
  13.     tail := head
  14.     for tail != nil{
  15.         lists = append(lists,tail)
  16.         tail = tail.Next
  17.     }
  18.     return help(lists,0,len(lists)-1)
  19. }
  21. func help(lists []*ListNode,start int,end int)*ListNode{
  22.     if start == end{
  23.         return lists[start]
  24.     }
  25.     mid := start + (end-start) / 2
  26.     lists[mid].Next = nil
  27.     l1 := help(lists,start,mid)
  28.     l2 := help(lists,mid+1,end)
  29.     l3 := merge(l1,l2)
  30.     return l3
  31. }
  33. func merge(l1 *ListNode,l2 *ListNode)*ListNode{
  34.     if l1 == nil{
  35.         return l2
  36.     }
  37.     if l2 == nil{
  38.         return l1
  39.     }
  40.     if l1.Val < l2.Val{
  41.         l1.Next = merge(l1.Next,l2)
  42.         return l1
  43.     }else{
  44.         l2.Next = merge(l2.Next,l1)
  45.         return l2
  46.     }
  47. }

6. 其他必须 掌握

剑指 Offer 06. 从尾到头打印链表 简单

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]

题解概要：

  1. 使用栈来保存数组的值，很符合栈的模式。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func reversePrint(head *ListNode) []int {
  9.     stack := []*ListNode{}           //创建栈
  10.     cur := head
  11.     for cur != nil{
  12.         stack = append(stack,cur)
  13.         cur = cur.Next
  14.     }
  15.     ans := make([]int,len(stack))
  16.     j := 0
  17.     for i := len(stack)-1;i >= 0;i--{
  18.         ans[j] = stack[i].Val
  19.         j++
  20.     }
  21.     return ans
  22. }

876. 链表的中间结点 简单

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

题解概要：

  1. 使用快慢指针，快指针一次走两步，慢指针一次走一步。当快指针走完时，慢指针恰好为中间节点。
  2. 需注意下中间节点的定义，处理下边界条件。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. import "fmt"
  9. func middleNode(head *ListNode) *ListNode {
  11.     fast := head
  12.     slow := head
  14.     /*边界条件可以画图或打印推导出来*/
  15.     for fast != nil && fast.Next != nil {
  16.         fast = fast.Next.Next     //快指针走两步
  17.         slow = slow.Next         //慢指针走一步
  18.     }
  20.     return slow
  23. }

2. 两数相加 中等

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

题解概要：

  1. 模拟两个数相加的过程，主要考虑进位的问题。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  9.     dummry := &ListNode{}    //设置虚拟头节点
  10.     tail := dummry
  11.     carry := 0
  12.     for l1 != nil || l2 != nil{
  13.         n1,n2 := 0,0
  14.         if l1 != nil{
  15.             n1 = l1.Val
  16.             l1 = l1.Next
  17.         }
  18.         if l2 != nil{
  19.             n2 = l2.Val
  20.             l2 = l2.Next
  21.         }
  23.         sum := n1 + n2 + carry
  24.         sum,carry = sum % 10,sum / 10
  25.         tail.Next = &ListNode{Val:sum}
  26.         tail = tail.Next 
  27.     }
  28.     //判断是否还有进位!
  29.     if carry != 0{
  30.         tail.Next = &ListNode{Val:carry}
  31.     }
  33.     return dummry.Next
  34. }

141. 环形链表 简单

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例 1：
image.png
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

题解概要：

leetcode官方对这道题解释很清楚，以下引自官方题解：

思路及算法
本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
链表 - 图8

细节

为什么我们要规定初始时慢指针在位置 head，快指针在位置 head.next，而不是两个指针都在位置 head（即与「乌龟」和「兔子」中的叙述相同）？

观察下面的代码，我们使用的是 while 循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始都置于 head，那么 while 循环就不会执行。因此，我们可以假想一个在 head 之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next，这样我们就可以使用 while 循环了。

当然，我们也可以使用 do-while 循环。此时，我们就可以把快慢指针的初始值都置为 head。

代码：

  1. func hasCycle(head *ListNode) bool {
  3.     if head == nil  || head.Next == nil {
  4.         return false
  5.     }    //特殊条件
  7.     slow := head         //慢指针
  8.     fast := head.Next    //快指针
  10.     for fast != nil && fast.Next != nil{    
  12.         if fast == slow{
  13.             return true
  14.         }
  15.         slow = slow.Next
  16.         fast = fast.Next.Next
  17.     }
  19.     return false
  21. }

142. 环形链表 II 中等

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

题解概要：

1.第一种方法可以使用哈希表，当第一次出现重复node时，就是环的入口。
2.第二种方法需要用到数学推导。
链表 - 图9
如上图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的2 倍。因此，我们有

a+(n+1)b+nc=2(a+b) ⟹ a=c+(n-1)(b+c)，构造系数。

有了 a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离。当n等于1时，a就等于c。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func detectCycle(head *ListNode) *ListNode {
  9.     if head == nil || head.Next == nil{
  10.         return nil
  11.     }
  13.     slow,fast := head,head
  15.     for fast != nil && fast.Next != nil{
  16.         slow = slow.Next
  17.         fast = fast.Next.Next
  18.         //相遇，说明存在环
  19.         if slow == fast{
  20.             cur := head
  21.             //接着slow和head每次都移动一个位置，相遇便是环的入口。
  22.             for cur != slow{
  23.                 cur = cur.Next
  24.                 slow = slow.Next
  25.             }
  26.             return slow
  27.         }
  28.     }
  30.     return nil
  31. }

160. 相交链表 简单

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
链表 - 图10
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

链表 - 图11
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

题解概要：

  1. 节点A遍历完后接着遍历节点B。节点B遍历完后继续遍历节点A，则节点相同时，即为第一个公共节点。

设「第一个公共节点」为 node ，「链表 headA」的节点数量为 aa ，「链表 headB」的节点数量为 bb ，「两链表的公共尾部」的节点数量为 cc ，则有：
头节点 headA 到 node 前，共有 a - ca−c 个节点；
头节点 headB 到 node 前，共有 b - cb−c 个节点；
链表 - 图12

考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：

指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a + (b - c)
a+(b−c)

指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b + (a - c)
b+(a−c)

如下式所示，此时指针 A , B 重合，并有两种情况：

a + (b - c) = b + (a - c)
a+(b−c)=b+(a−c)

若两链表 有 公共尾部 (即 c > 0c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c = 0c=0 ) ：指针 A , B 同时指向 nullnull 。
因此返回 A 即可。

链表 - 图13

代码：

  1. func getIntersectionNode(headA, headB *ListNode) *ListNode {
  3.     nodeA,nodeB := headA,headB
  5.     for nodeA != nodeB{
  6.         //A遍历完了，就链接到B
  7.         if nodeA != nil {
  8.             nodeA = nodeA.Next
  9.         }else{
  10.             nodeA = headB
  11.         }
  12.         //B遍历完了，链接到A，第一次相遇时就为公共节点。
  13.         if nodeB != nil {
  14.             nodeB = nodeB.Next
  15.         }else{
  16.             nodeB = headA
  17.         }
  19.     }
  21.     return nodeA
  23. }

143. 重排链表 中等

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

题解概要：

  1. 借助线性表，重新排列链表即可。

代码：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func reorderList(head *ListNode)  {
  9.     stack := []*ListNode{}
  10.     tail := head
  11.     //将节点压入栈
  12.     for tail != nil{
  13.         stack = append(stack,tail)
  14.         tail = tail.Next
  15.     }
  16.     //特殊判断
  17.     if len(stack) < 3{
  18.         return
  19.     }
  20.     l,r := 0,len(stack)-1
  21.     node := &ListNode{}
  22.     for l <= r{
  23.         node.Next = stack[l]
  24.         node = node.Next
  25.         node.Next = nil
  26.         l ++
  27.         if l <= r{
  28.             node.Next = stack[r]
  29.             node = node.Next
  30.             node.Next = nil
  31.             r --
  32.         }
  33.     }
  34. }

328. 奇偶链表

146. LRU 缓存

460. LFU 缓存