LeetCode-25.k个一组反转链表

发表于 分类于

题目描述

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

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

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

进阶：

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

题解

递归法：

  1. 链表需要分组后对每组进行反转，然后将反转后的各组进行连接；
  2. 终止条件： 当进行到最后一个分组，即不足k次遍历到链表尾（0次也算），就将剩余的部分直接返回。
  3. 返回值： 每一级要返回的就是翻转后的这一分组的头，以及连接好它后面所有翻转好的分组链表。
  4. 本级任务： 对于每个子问题，先遍历k次，找到该组结尾在哪里，然后从这一组开头遍历到结尾，依次翻转，结尾就可以作为下一个分组的开头，而先前指向开头的元素已经跑到了这一分组的最后，可以用它来连接它后面的子问题，即后面分组的头。
1
2
3
4
5
6
7
8
9
// 单向链表
class ListNode {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
      self.val = val
      self.next = nil
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
  var tail = head
  // 注意边界，遍历k次，tail最终是k+1节点，也就是下一组链表的头节点
  for _ in 1 ... k {
    if tail == nil {
      return head
    }
    tail = tail?.next
  }
  
  // 组内元素反转
  var pre: ListNode? = nil
  var cur: ListNode? = head
  while(cur !== tail){
    let temp = cur?.next
    cur?.next = pre
    pre = cur
    cur = temp
  }
  // head指针指向的是未反转前的第一个节点，也就是反转后的最后一个节点。
  // 将head.next指向下一组反转后的链表的头节点
  head?.next = reverseKGroup(tail, k)
  return pre
}