如何一气呵成细节较多的《K 个一组翻转链表》

[zhuanyongxigua]

这道题由于是每一组 k 个节点都需要进行反转，所以你需要先搞清楚剩下的节点中是否有 k 这么多个节点，这不可能在一个 n（节点数量）次的遍历中就完全解决问题。你需要知道这一次的将要到达的结尾，这一次的开头和上一次的结尾。这就是你需要维护的状态。

第一次完全通过写出来的东西，肉眼可见的狼狈，为了解决问题，除了上诉的必要状态之外，我还加了好几个其他的状态：

var reverseKGroup = function(head, k) {
  if (head === null || k === 0) {
    return head
  }
  let tail = head
  let num = 0
  let numStart = head
  let numTail = head
  let isReverse = false
  let reverseNum = 0
  let lastTail = head
  let curHead = null
  while (tail !== null || isReverse) {
    if (isReverse) {
      if (num > 1) {
        if (num === k) {
          curHead = numStart
        }
        let nextHead = numStart.next
        numStart.next = numTail
        numTail = numStart
        numStart = nextHead
        num--
      }
      if (num === 1) {
        if (reverseNum !== 0 && lastTail !== null) {
          lastTail.next = numStart
        }
        lastTail = curHead
        numStart.next = numTail
        reverseNum++
        isReverse = false
        num = 0
        if (reverseNum === 1) {
          head = numStart
        }
        numStart = tail
      }
    } else {
      num++
      tail = tail.next
      if (num === k) {
        numTail = tail
        isReverse = true
      }
    }
  }
  return head
}

过多的状态造成了维护状态很痛苦，这样就会出现很多很讨厌的细节，很难快速的写对，没有清晰的思路，这将造成下次写的时候还是一样的不会写，需要从头思考。

人类解决这种问题的较为通用的方法，就是分类，在代码中就是拆分模块。想一想，这里有什么是可以拆分的？显而易见，就是反转 k 个之内的链表。我们就可以针对这个局部的需求来单独封装一个函数。

这个函数的参数和返回值应该如何设计呢？head 一定是必须的，这个函数必须要知道从哪儿开始。不过这一个参数显然不够，还需要知道 tail 或者是 k。选择后者，好处是可以尝试递归。这里我们选择前者，更容易理解。对于返回值，可有可无。这里我们选择没有返回值，穿进去的 head 就会变成 tail，tail 会变成 head。

写一个在知道 head 和 tail 时情况下，反转这一段链表的函数：

function reverseGroup (head, tail) {
  if (head === tail) return
  // 修改了 tail 这个变量的指向，真是的 tail 节点依然在那里
  tail.next = null
  tail = null
  while (head !== null) {
    const nextHead= head.next
    head.next = tail
    tail = head
    head = nextHead
  }
}

主函数好了一点点，经常变化的状态由八个变成了四个，但是还是不够好，状态还是偏多，但是思路对比之前已经清晰了很多：

var reverseKGroup = function(head, k) {
  if (
    head === null
    || head.next === null
    || k <= 1
  ) return head

  const protectedHead = {
    value: -1,
    next: head
  }
  let num = 0
  let paramHead = head
  let paramTail = protectedHead
  let lastTail = paramTail
  while (paramTail !== null) {
    if (num < k) {
      num++
      paramTail = paramTail.next
    } else {
      const nextParamHead = paramTail.next
      reverseGroup(paramHead, paramTail)
      lastTail.next = paramTail
      lastTail = paramHead
      paramHead = nextParamHead
      paramTail = nextParamHead
      num = 1
    }
  }
  if (num <= k) {
    lastTail.next = paramHead
  }
  return protectedHead.next
}

这里的四个状态，除了在文章开头我们提出的必须的三个之外之外，还多了一个 num，用来判断当前剩下的节点数量，是否有 k 个。从代码从可以看到，这个状态非常的麻烦，维护它的地方很多，也很散乱。所以我们下一步就可以考虑把它抽离。

它是用来判断剩下节点数量是否满足要求的，那我们可不可以写一个函数，当满足 k 个节点的时候，返回这一组的 tail 节点，不满足的时候返回 null？

function getTail (head, k) {
  while (k > 1 && head !== null) {
    head = head.next
    k--
  }
  return head
}

再优化一下，还有三个需要维护的状态：

var reverseKGroup = function(head, k) {
  if (
    head === null
    || head.next === null
    || k <= 1
  ) return head
  const protectedHead = {
    value: -1,
    next: head
  }

  let paramHead = head
  let paramTail = protectedHead
  let lastTail = paramTail
  while (paramTail !== null) {
    let paramTail = getEnd(paramHead, k)
    if (paramTail === null) {
      lastTail.next = paramHead
      break
    }
    const nextParamHead = paramTail.next
    reverseGroup(paramHead, paramTail)
    lastTail.next = resultTail
    lastTail = resultHead
    paramHead = nextParamHead
    paramTail = nextParamHead
  }
  return protectedHead.next
}

优化到这里，基本上已经达到文章开头提到的最简化的状态了。可如果你追求简洁了，依然可以继续优化。

仔细观察，while 中的判断条件是 paraTail，也就是上一次的结尾，可在 while 里面，如果发现 paramTail 为 null，就可以直接 break 了。所以在剩余的节点数量不足 k 个的时候，我们是不需要在循环的外面适用这个变量的。可如果剩余的节点数量刚好等于 k 个怎么办？可以用 paramHead 来判断。同时也可以直接用 head 来代替 paramHead。如果题目要求你知道初始的 head，那可以用一个 const 声明的常量来存一下初始的 head，这题并不需要。

最终的版本，只有一个需要一直维护的状态，到了这里，你甚至都不再需要刻意的背什么东西，就可以顺着思路写下去了：

var reverseKGroup = function(head, k) {
  if (
    head === null
    || head.next === null
    || k <= 1
  ) return head
  const protectedHead = {
    value: -1,
    next: head
  }

  let lastTail = protectedHead
  while (head !== null) {
    let curTail = getEnd(head, k)
    if (curTail === null) {
      lastTail.next = head
      break
    }
    const nextHead = curTail.next
    reverseGroup(head, curTail)
    lastTail.next = curTail
    lastTail = head
    head = nextHead
  }
  return protectedHead.next
}

完整的代码：

export function reverseGroup (head, tail) {
  if (head === tail) return
  tail.next = null
  tail = null
  while (head !== null) {
    const nextHead = head.next
    head.next = tail
    tail = head
    head = nextHead
  }
}

function getEnd (head, k) {
  while (k > 1 && head !== null) {
    head = head.next
    k--
  }
  return head
}

var reverseKGroup = function(head, k) {
  // 这种就是白给的，看一眼就记住了
  if (
    head === null
    || head.next === null
    || k <= 1
  ) return head

  const protectedHead = {
    value: -1,
    next: head
  }
  let lastTail = protectedHead
  while (head !== null) {
    let curTail = getEnd(head, k)
    if (curTail === null) {
      lastTail.next = head
      break
    }
    const nextHead = curTail.next
    reverseGroup(head, curTail)
    lastTail.next = curTail
    lastTail = head
    head = nextHead
  }
  return protectedHead.next
}