[Leetcode 25] K 个一组翻转链表

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
输入是链表的头节点 head ,每 k 个节点一组进行翻转,返回修改后的链表。
 
说明:
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
 
示例 1:
notion image
示例 2:
notion image
 
 
 

解法一:双 / 三指针迭代(推荐)

这题的本质是:把链表按照 k 个一组进行切片,每一片翻转,然后再把这些片段按原顺序连接回去。
为了能优雅地处理开头和每段的拼接,一般都会创建一个 dummy 节点作为链表的起点。
核心逻辑是:
  • 维护两指针
    • left 指向待反转段的前一个节点;
      right 用来定位反转段末的后一个节点(半开区间 (left, right))。
  • 当两者之间的有 k 个节点时,进行区间反转:把 (left, right) 之间的链表就地反转。并返回新段的尾节点作为下一段的 left
  • 再继续下一段。
复杂度
  • 时间:O(n) 整段链表只会扫描一遍,每一段只翻转一次,因此整个过程是线性的。
  • 空间:O(1) 只用常数级指针,不借助额外结构。

解法二:递归

  1. 先判断当前剩余的链表里,节点数量是否够 k 个
      • 如果不够,就不需要翻转
      • 如果够,用简单的 for 循环实现这 k 个节点的翻转
  1. 递归处理第 k+1 个开始的后面部分的翻转
  1. 然后把两段拼在一起
复杂度
  • 时间:O(n) 每段翻一次,整条链表只遍历一次。
  • 空间:O(n/k)(递归栈)
 
 
 
上一篇
[Leetcode 23] 合并 K 个升序链表
下一篇
[Leetcode 32] 最长有效括号