链表的反转和删除算法策略

Liu Bowen

Liu Bowen / 2020, 八月, 01

链表是基于离散存储（或称链式存储），而非像 array 或 slice 之类数据结构使用的顺序存储。对于链表来说，在不能通过索引访问的情况下，只能通过遍历的形式来查找指定项，即它的查询时间复杂度为 O(N)，插入的时间复杂度为 O(1)。

链表遍历的迭代法模板如下：

go
func traversalLinkedList(head *ListNode) *ListNode {
  current := head

  for current != nil {
    // ... do something you want

    // 通过 Next 属性移动到链表的下一节点
    current = current.Next
  }

  // ...
}

新增链表节点的方法

对于链表新增节点的方式存在头插法和尾插法，即

  1. 当新节点始终是通过成为新的头节点的方式插入到链表中时，即为头插法；

  2. 当新节点始终时通过成为新的尾节点的方式插入到链表中时，即为尾插法。

删除链表中的项

删除链表的基本策略：

  1. 对于可能出现的头节点删除的场景，通过构建一个虚拟的 哨兵节点 来简化头节点的删除，即将头节点删除，转化为非头节点删除问题；

  2. 通过调整节点的 Next 属性来实现链表节点删除。

删除链表中的指定项

删除链表中等于给定值 val 的所有节点。

easy 203 移除链表元素

删除链表中的指定项，存在两种 case：

  1. 待删除节点是头节点；

  2. 待删除节点是非头节点；

当待删除节点是非头节点时，我们可以轻松通过调整待删除节点的前一节点的 Next 实现删除指定节点；

go
prev.Next = current.Next

当待删除节点为头节点时，此时为了便捷处理头节点删除，在链表头部新增一个虚拟节点实现头节点删除。

go
sentinel := &ListNode{
  Next: head,
}
current, prev := head, sentinel

for current != nil {
  // ... 删除节点
}

return sentinel.Next

最终实现代码如下：

go
func removeElements(head *ListNode, val int) *ListNode {
  if head == nil {
    return head
  }
  sentinel := &ListNode{
    Next: head,
  }
  current, prev := head, sentinel
  for current != nil {
    if current.Val == val {
      prev.Next = current.Next
    } else {
      prev = current
    }
    current = current.Next
  }
  return sentinel.Next
}

删除链表中的重复项

对于删除链表中的重复项的场景存在两种情况：

  1. 保证结果链表中的每个节点的值对于整个链表中唯一。

  2. 保证结果链表中不包含之前出现过重复的所有节点。

保证结果唯一

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

easy 83 删除排序链表中的重复元素

对于给定问题，对于去重操作的抽象化，可以得到以下思考路径：

  1. 因为仅是为了删除节点，那么不可能需要删除头节点，那么不需要构建哨兵节点。

  2. 需要在遍历中存在两个指针，一个指针指向非重复项，仅在下一个节点为非重复项时移动；一个指针为遍历指针，即在遍历过程中遍历链表的每一个节点；

    每次遍历指针移动时，都应该与非重复项指针比较，确定是否能够移动非重复项指针。

  3. 待遍历结束时，非重复项指针即为结果链表的尾节点。

根据以上要点得到以下实现代码：

go
func deleteDuplicated(head *ListNode) *ListNode {
  if head == nil {
    return head
  }

  slow, fast := head, head

  for fast != nil {
    // slow 指针将跳过所有的重复项，直接到非重复项
    if slow.Val != fast.Val {
      slow.Next = fast
      slow = slow.Next
    }
    fast = fast.Next
  }

  slow.Next = nil

  return head
}

保证结果不出现重复过的项

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

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

在此场景下，只要一项出现了重复，那么不仅仅需要删除重复的项，还需要删除自身，那么：

  1. 可能出现删除头节点的场景，首先构建一个虚拟哨兵节点；

    go
    sentinel := &ListNode{
  Next: head,
}

  2. 当下一个节点 current.Next 与下下个节点 current.Next.Next 相等时进入额外遍历，在额外遍历中找到不等项，将当前节点的 Next 指向该不等项实现删除所有出现重复的项，即 current.Next = lastOfDuplicates.Next。

    go
     /*
   若下一项与下下一项相等时，通过迭代找到不等项，直接通过 current.Next = node.Next
   实现删除所有出现过重复的项
 */
if current.Next.Val == current.Next.Next.Val {
  // 从重复项开始找到下一个重复的项
  node := current.Next
  for node.Next != nil && node.val == node.Next.Val {
    node = node.Next
  }
  // 此时 node 为当前重复项的最后一项
  current.Next = node.Next
  // 此处无 current 指针移动
} else {
  current = current.Next
}

    在上文代码中，存在一个细节在于 current.Next = node.Next 之后，没有 current 指针的移动。因为我们无法确定新的 current.Next 与新的 current.Next.Next 是否存在重复，那么需要在下轮遍历中验证，故在存在 current.Next 修改的场景下，不存在 current 指针移动操作。即 current.Next 的修改操作与 current 指针移动操作是互斥的。

最终实现如下：

go
func deleteDuplicates(head *ListNode) *ListNode {
  sentinel := &ListNode{
    head: Next
  }
  current := sentinel

  for current.Next != nil && current.Next.Next != nil {
    if current.Next.Val == current.Next.Next.val {
      node = current.Next
      if node.Next != nil && node.Val == node.Next.Val {
        node = node.Next
      }
      current.Next = node.Next
    } else {
      current = current.Next
    }
  }

  return current.Next
}

删除链表中的倒数第 N 项

给定一个链表，删除链表的倒数第 n（始于 1）个节点，并且返回链表的头结点。

medium 19 删除链表的倒数第 N 个节点

对于此场景，可能出现删除头节点的情况，那么为了简化头节点的删除，可以构建一个 哨兵节点 来将删除头节点的场景转换为非头节点删除。

与普通地删除特定链表中的项不同的是，删除倒数第 n 项，即表示在遍历到链表尾端时，需要回探到倒数第 n 个节点，那么快慢指针策略呼之欲出。

那么接下来的问题核心就在于如何定义快慢指针的移动策略来解决我们找到倒数第 n 个节点。我们可以定义快指针先走 n 步，然后 fast 与 slow 指针齐头并进，直到 fast 到达尾端时，即表示 slow 已经到达倒数第 n 个节点。而最终目标是要我们删除此时的 slow 指针节点，那么必须知道 slow 指针节点之前的节点。这里有两种处理方式，一种是通过额外变量保存 slow 的前一节点，一种是在移动 fast 指针时，多走一步，即相当于 slow 少走一步，那么当 fast 到达尾端时，此时 slow 即到达待删除节点的前一节点。

go
// leetcode 中保证 n 有效，故排除了对异常 n 的处理
func removeNthFromEnd(head *ListNode, n int) *ListNode {
  sentinel := &ListNode{
    Next: head,
  }
  fast, slow := sentinel, sentinel

  /*
    fast 指针先走 n+1(在参数 n 基础上多走 1 步) 步；若没有 n+1，那么最终 slow 指针将停
    留在待删除节点，而非待删除节点的前一节点
  */
  n++
  for n > 0 {
    n--
    fast = fast.Next
  }

  for fast != nil {
    fast = fast.Next
    slow = slow.Next
  }
  // 此时 slow.Next 即为待删除的倒数第 n（n>0） 项
  slow.Next = slow.Next.Next

  return sentinel.Next
}

反转链表

反转操作是链表中的一种常规操作，最终目标是实现将原有头节点，变为尾节点，第 n(1 ≤ n ≤ 链表长度) 个节点变为第 len-n+1 个节点。

反转整个链表

反转一个单链表。

easy 206 反转链表

反转整个链表即需要构建整个链表的所有链接的反向链接，那么在迭代时就需要临时变量存储中间节点，通过临时变量不断地临时存储下一节点需要链接的节点：

  1. 缓存 next 节点

    go
    next = current.Next

  2. 反转 current.Next 节点为前一节点

    go
    current.Next = prev

  3. 将 prev 指针移动到当前节点，以备下一节点使用

    go
    prev = current

  4. 通过 1 中的缓存，而不是 current.Next（此时已经被反转）移动到下一节点

    go
    current = next

最终实现代码如下：

go
// 迭代法
func reverseList(head *ListNode) *ListNode {
  current := head
  var prev *ListNode

  for current != nil {
    next := current.Next
    current.Next = prev
    prev = current
    current = next
  }

  return prev
}

另一种基于迭代和临时变量的实现，是在于始终构建一个临时变量 保持对当次迭代时的头节点引用，以通过头插法将反转的节点恢复到链表中。这种移动方式是一种 基于原始头节点（而不是当前头节点或最终头节点）的移动，本质上是将头节点的移动行为转变为头插法新增节点行为，进而实现指定节点反转到头部。当头节点的下一节点为空时，即表示头节点已经移动到尾端成为新的尾节点，即完成了整个链表的反转：

  1. 构建一个虚拟哨兵节点，用于保持对 当次头节点 的引用（而不是原始头节点或最终头节点）；

    go
    sentinel := &ListNode{
  // 初始头节点为 head，故此时引用 head
  Next: head
}

  2. 构架一个迭代，在原始头节点的下一节点为 nil 时，退出迭代；

    go
    for head.Next != nil {
  // ...
}

  3. 在迭代中始终选中原始头节点的下一节点为待反转节点，即后续通过头插法插入到头部的节点；

    0(sentinel) -sentinel.Next-> 1(head) -head.Next-> 2 -> 3 -> 4
    go
    next := head.Next

  4. 从链表中删除待反转节点；

    0(sentinel) -sentinel.Next-> 1(head) -head.Next -> 3 -> 4
                                                   ^
                                                   |
                                                   2
    go
    head.Next = head.Next.Next

  5. 将待反转链接到当前的头部（而不是原始头部）节点；

    0(sentinel) -sentinel.Next-> 1(head) -head.Next -> 3 -> 4
                                ^
                                |
                                2
    go
    next.Next = sentinel.Next

  6. 通过头插法，重新将待反转节点加入到链表中，完整一次节点反转。

    0(sentinel) -sentinel.Next-> 2 -> 1(head) -head.Next -> 3 -> 4
    go
    sentinel.Next = next

最终实现代码如下：

go
func reverseList(head *ListNode) *ListNode {
  if head == nil {
    return head
  }
  sentinel := &ListNode{
    Next: head,
  }

  for head.Next != nil {
    next := head.Next
    head.Next = head.Next.Next
    next.Next = sentinel.Next
    sentinel.Next = next
  }

  return sentinel.Next
}

而对于递归法反转，我们首先确定一个大前提是，对于所有的递归，不进入压栈思考，转而将递归操作转化为对一类操作的抽象。**最重要的是明确递归函数的功能定义。**那么我们可以得到以下操作的抽象：

  1. 当下一节点不存在时，返回当前节点。不再进行递归操作。

    go
    if head.Next == nil {
  return head
}

  2. 递归反转 next ~ tail 部分，这一部分 并不 进入递归栈进行思考，而是仅作为递归的功能抽象，即

    go
    staleTail := reverseList(head.Next)
// ...
return staleTail

    对于上文代码来说，我们仅仅思考此时的 staleTail 变量保存的是 head.Next 部分反转后的头节点。

    before
1 -> reverseList(2 -> 3 -> 4 -> nil)

after
1 -> 2 <- 3 <- 4(staleTail)
     |
     v
    nil

  3. 在经过上一步反转后，此时被递归后的部分的尾节点为 head.Next，后续将其 Next 接入到 head 节点；

    go
    head.Next.Next = head

    1 <-> 2(head.Next.Next) <- 3 <- 4(staleTail)
            |
      x 不再引用为 nil
            |
            v
           nil

  4. 在上一步对反转部分的连接构建完成后，断开原有的 head.Next 连接。

    go
    head.Next = nil

通过以上思考路径，得到最终实现代码：

go
func reverseList(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
    return head
  }
  staleTail := reverseList(head.Next)
  // 将反转后的部分的新的尾节点指向 head
  head.Next.Next = head
  // 断开原有对 head.Next 的引用，使得此时的 head 变量成为最终的 tail 节点
  head.Next = nil
  return staleTail
}

反转链表的区间

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。(1 ≤ m ≤ n ≤ 链表长度。)

medium 92 反转链表 II

若基于链表迭代思考实现 m 到 n 的链表部分反转的话：

  1. 因为待反转的部分可能包含头节点，为了便捷处理函数返回，我们通过构造一个虚拟哨兵节点来将头节点 case 转换为非头节点的 case。

    go
    sentinel := &ListNode{
  Next: head,
}

// ...
return sentinel.Next

  2. 首先 prev 指针首先前进到第 m-1 个节点，因为第 m 个节点为稍后待反转节点；

    go
    prev := sentinel
for i := 1; i < m; i++ {
  prev = prev.Next
}

  3. 根据 头插法 反转 m ~ n 部分的节点；

    before
1(prev) -> 2(partHead) -> 3(next) -> 4 -> 5

after
1(prev) -> 2(partHead) -> 3(next) -> 4 -> 5
    go
    partHead := prev.Next
for i := m; i < n; i++ {
  next := partHead.Next
  partHead.Next = partHead.Next.Next
  next.Next = prev.Next
  prev.Next = next
}

  4. 返回结果

    go
    return sentinel.Next

这里值得注意的是为什么第三步可以实现头插法反转区间链表？这里借鉴了上文 反转整个链表 中通过头插法的迭代方式反转链表的方式。在当次迭代中始终取原头节点的下一个节点来完成一次反转：

  1. 保存待反转节点 next；

    go
    next := partHead.Next

  2. 断开与待反转节点的连接；

    1(prev) -prev.Next-> 2(partHead) -partHead.Next -> 4 -> 5
                                                    ^
                                                    |
                                                  3(next)
    go
    partHead.Next = partHead.Next.Next

  3. 待反转节点重新接入链表，即待反转节点 next 指向原反转区间的头部节点，此时待反转节点将成为反转区间的头节点；

    1(prev) -prev.Next-> 2(partHead) -partHead.Next -> 4 -> 5
                          ^
                          |
                        3(next)
    go
    next.Next = prev.Next

  4. 依据 prev 节点构建新的反转区间的头节点，完成一次区间反转：

    1(prev) -prev.Next-> 3(next) -> 2(partHead) -partHead.Next -> 4 -> 5
    go
    prev.Next = next

  5. 回到 1 继续迭代 partHead.Next 节点，并将其反转到区间头部

本质上，以上反转的方式是始终保持了对原头节点的引用，每次反转头节点的下一节点到区间头部成为新的头节点，那么在完成反转时，原头节点将成为区间的尾节点。

根据以上操作抽象，得到以下最终实现代码：

go
func reverseBetween(head *ListNode, m, n int) *ListNode {
  sentinel := &ListNode{
    Next: head,
  }
  prev := sentinel

  for i := 1; i < m; i++ {
    prev = prev.Next
  }

  /*
    借助头插法实现区间节点反转
  */
  partHead := prev.Next
  for i := m; i < n; i++ {
    // 保存待反转节点
    next := partHead.Next
    // 从前一节点断开待反转节点
    partHead.Next = partHead.Next.Next
    // 插入到反转部分的头部，即头插法
    next.Next = prev.Next
    // 恢复非反转部分对反转部分的头节点的连接
    prev.Next = next
  }

  return sentinel.Next
}

两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

medium 24 两两交换链表中的节点

两两交换链表中的节点的问题本质是 反转链表的区间 的特殊版本，即反转的区间长度为 2，且操作了多次。那么得到以下抽象操作步骤：

  1. 因为存在对头节点的操作，为了规避头节点的边界情况处理，那么构建一个哨兵节点；

    go
    sentinel := &ListNode{
  Next: head,
}

  2. 构建链表的迭代框架；

    go
    // current 为参考节点
current, prev := sentinel.Next, sentinel

for current != nil {
  // ...
}

  3. 借鉴前文 头插法 反转链表的思路，在一次迭代中，反转相邻节点；

    go
    // 保存待反转节点
next = current.Next
// 从链表中断开待反转节点
current.Next = next.Next
// 将待反转节点指向目标区间头部
next.Next = prev.Next
// 将待反转节点重新接入链表中，完成一次节点反转
prev.Next = next

    因为不能保证待反转节点一定有下一个节点，那么当不存在待反转节点（参考节点的下一节点），即无法完成两两节点交换时，此时已经表示已经完成了链表中所有可交换的操作，那么返回最终结果链表：

    go
    if next == nil {
  return sentinel.Next
}

  4. 调整 prev 和 current 指针，继续下一次两两交换；

    go
    // 此时 current 为反转区间的 tail 节点，故取 Next 即到达下一反转区间
prev = current
current = current.Next

最终实现代码如下：

go
func swapPairs(head *ListNode) *ListNode {
  if head == nil {
    return head
  }
  sentinel := &ListNode{
    Next: head,
  }
  current, prev := sentinel.Next, sentinel
  for current != nil {
    next := current.Next

    if next == nil {
      return sentinel.Next
    }

    current.Next = next.Next
    next.Next = prev.Next
    prev.Next = next

    prev = current
    current = current.Next
  }

  return sentinel.Next
}

K 个一组反转链表

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

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

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

hard 25 K 个一组反转链表

与 k 个一组反转相比较，两两交换链表中的节点 是其 k=2 的场景。同样地，我们可以将 k 个一组反转链表问题转换为 反转链表的区间 的操作执行了多次的场景。那么经过以上问题解析，得到以下抽象操作路径：

  1. 因为存在对头节点的操作，故为了规避头节点处理，构建一个哨兵节点；

    go
    sentinel := &ListNode{
  Next: head,
}

  2. 构建链表迭代框架；

    go
    current, prev := sentinel.Next, sentinel
for current != nil {
  // ...
}

  3. 在迭代中，验证当前参考节点至整个链表尾节点是否能够完成 k 个反转，否定时，表示当前已经完成了所有可完成的 k 个一组反转节点的操作，直接返回结果链表；

    go
    next := current.Next

tail := prev
// i 迭代 k 次
for i := 0; i < k; i++ {
  tail  = tail.Next
  if tail == nil {
    return sentinel.Next
  }
}

  4. 当经过上一步验证可完成 k 个节点反转时，执行如同 反转链表的区间 相似的基于头插法的四步反转操作；

    go
    for i := 0; i < k-1; i++ {
  next := current.Next
  // 从链表中移除待反转节点 next
  current.Next = next.Next
  // 将带反转节点链接到反转区间的头节点
  next.Next = prev.Next
  // 重新在链表中接入待反转节点，完成反转区间中的一个节点反转
  prev.Next = next
}

  5. 参考节点 current 在区间完成反转后，由原来的区间头节点变为区间尾节点，故直接通过参考节点的 Next 进入到下一个待反转区间；

    go
    prev = current
current = current.Next

最终实现代码如下：

go
func reverseKGroup(head *ListNode, k int) *ListNode {
  if head == nil {
    return head
  }
  sentinel := &ListNode{
    Next: head,
  }
  current, prev := sentinel.Next, sentinel
  for current != nil {
    // 是否可执行 k 个节点反转
    tail := prev
    for i := 0; i < k; i++ {
      tail = tail.Next
      if tail == nil {
        return sentinel.Next
      }
    }

    // 执行 k 个节点反转
    for i := 0; i < k-1; i++ {
      next := current.Next
      // 从链表中移除待反转节点 next
      current.Next = next.Next
      // 将带反转节点链接到反转区间的头节点
      next.Next = prev.Next
      // 重新在链表中接入待反转节点，完成反转区间中的一个节点反转
      prev.Next = next
    }

    // 进入下一个反转区间
    prev = current
    current = current.Next
  }

  return sentinel.Next
}

归纳链表反转的思考路径

不论是反转整个链表，还是链表区间，在基于存在一个反转区间外节点保持对当前迭代中链表头节点的引用的 前提下，一种统一的反转节点的思考路径为基于 头插法 的链表节点反转：

  1. 缓存待反转节点；

  2. 从链表中删除待反转链接；

  3. 待反转节点通过区间外节点链接到上次迭代结果头部（不是原始头部），成为新的头节点；

  4. 通过头插法和区间外节点，恢复与待反转链表的链接；

本质上以上思考路径始终是存在一个 反转区间之外的节点 保存对反转区间的头节点的引用，每次节点的反转都是基于一个 参考节点 进行。每次都反转参考节点的 下一节点 至反转区间头部，成为新的反转区间头节点。

经过以上 easy，medium，hard 不同难度题目实践归纳，基于头插法反转策略可灵活运用于多种反转策略中，真正实现一个原则，多种反转策略。