轶哥

妄图改变世界的全栈程序员。

K个一组翻转链表

LeetCode 25. K 个一组翻转链表 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
LintCode 450. K组翻转链表 https://www.lintcode.com/problem/reverse-nodes-in-k-group/

这是一道用常规思路就能解的算法题。目标清晰、题目易懂,不涉及复杂的算法。

按照题目要求,遍历链表,遍历的同时每经过k个节点就进行一次翻转。需要注意的是,第一次翻转后,记录下整个链表的head作为返回值。从第二次翻转开始,需要将之前翻转过的最后一个结点与新翻转后的第一个结点相连。

K个一组翻转链表

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
export const reverseKGroup = function (head, k) {
  let sum = 0 // 记录进行的结点个数
  let start = head // 记录每次翻转的第一个元素
  let res = head // 返回值:如果进行过翻转,则为第一次翻转的最后一个结点
  const queue = [] // 使用队列,方便连接上一次翻转的链表,最大长度为2
  while (head) { // 遍历一次链表
    if (++sum === k) { // 如果经过了k个结点,则翻转从start到head的一段结点
      const headNext = head.next
      queue.push(start) // 计入队列
      let next = head.next
      for (let i = 0; i < sum - 1; i++) { // 翻转结点
        const tmp = start.next
        start.next = next
        next = start
        start = tmp
      }

      start.next = next // 最后一个结点

      if (queue.length === 1) { // 判断是否为第一次翻转
        res = start
      } else {
        const la = queue.shift() // 连接上一次翻转的链表
        la.next = head
      }
      sum = 0 // 重置计数
      start = headNext
      head = headNext
    } else {
      head = head.next
    }
  }

  return res
}

leetcode-25

以往的算法题,暴力解法通常都无法通过测试,这题不需要什么操作技巧,就按题目要求的作解即可,编写过程中需要考虑清楚数据是如何变化的,做好边界条件的处理即可。

这道题还可以使用来解答。不妨再进一步思考,从后往前以k个为一组进行翻转如何实现?

这道题和合并K个排序链表算是链表中的少见的难题,其实这两道题整体思路都不复杂。

这是我的算法练习解题记录https://github.com/yi-ge/js-practice。欢迎加我微信探讨算法!

打赏
交流区

暂无内容

尚未登陆
发布
  上一篇 (Linux安装无线网卡驱动通用方法)
下一篇 (树莓派4变身旁路由)  

评论回复提醒