跳到主要内容

25. K 个一组翻转链表

题目描述​

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

示例1

输入：head = [1,2,3,4,5], k = 2

输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3

输出：[3,2,1,4,5]

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 1 <= Node.val <= 100
  • 1 <= k <= 50

出处：LeetCode

解法一：递归​

思路​

我们可以使用递归来翻转链表中的每 k 个节点。我们定义一个递归函数 reverse，函数的参数是两个节点 node1 和 node2，分别表示要翻转的 k 个节点的前一个节点和后一个节点。在递归函数中，我们首先判断 node1 和 node2 是否为空，如果其中有一个为空，则返回另一个节点。然后，我们翻转 node1 和 node2 之间的 k 个节点。最后，我们返回 node2 节点。

实现​

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  if (head === null) {
    return null;
  }

  let node1: ListNode | null = head;
  let node2: ListNode | null = head;

  for (let i = 0; i < k; i++) {
    if (node2 === null) {
      return head;
    }

    node2 = node2.next;
  }

  const newHead = reverse(node1, node2);
  node1.next = reverseKGroup(node2, k);

  return newHead;
}

function reverse(node1: ListNode | null, node2: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur: ListNode | null = node1;

  while (cur !== node2) {
    const next = cur!.next;
    cur!.next = prev;
    prev = cur;
    cur = next;
  }

  return prev;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是链表的长度
  • 空间复杂度：O(1)O(1)

解法二：迭代​

思路​

我们也可以使用迭代来翻转链表中的每 k 个节点。我们定义一个哑节点 dummy，然后定义一个指针 prev 指向哑节点。然后我们遍历链表，每次迭代时，我们将两个相邻的节点 node1 和 node2 分别指向 prev.next 和 prev.next.next。然后，我们将 prev.next 指向 node2，node1 的 next 指针指向 node2 的 next 节点，node2 的 next 指针指向 node1。最后，我们将 prev 指针指向 node1，继续迭代。

实现​

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode(0);
  dummy.next = head;

  let prev = dummy;

  while (prev.next !== null) {
    let node1 = prev.next;
    let node2 = prev.next;

    for (let i = 0; i < k; i++) {
      if (node2 === null) {
        return dummy.next;
      }

      node2 = node2.next;
    }

    prev.next = reverse(node1, node2);
    node1.next = node2;
    prev = node1;
  }

  return dummy.next;
}

function reverse(node1: ListNode | null, node2: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur: ListNode | null = node1;

  while (cur !== node2) {
    const next = cur!.next;
    cur!.next = prev;
    prev = cur;
    cur = next;
  }

  return prev;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是链表的长度
  • 空间复杂度：O(1)O(1)