25. K 个一组翻转链表

题目描述

输入链表的头节点 head 和正整数 k，链表用数组表示。k 不超过链表长度。

从头开始每 k 个节点分成一组，把每组内的节点顺序倒过来。最后不足 k 个的节点保持原顺序。

必须调整节点本身的连接，不能只换节点里的值。返回处理后链表的头节点。

示例 1

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

解释：分组为 [1,2]、[3,4]、[5]，前两组各自翻转，最后一组不足 2 个不动。

示例 2

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

解释：分组为 [1,2,3]、[4,5]，只翻转第一组。

数据范围

链表节点数记为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶：能否只用 O(1) 的额外空间完成？

解题思路：分组迭代反转

先检查一组是否有 k 个节点，保存组后节点；用标准指针反转这段区间，再接回前缀。

为什么正确

group_prev 前面的组已翻转；每次只翻转完整的 k 个节点。

复杂度分析

时间 O(n)，额外空间 O(1)。

易错点

必须先确认组长；不足 k 个的部分不能翻转。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def reverseKGroup(self, head, k):
        dummy = ListNode(0, head)
        group_prev = dummy
        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if kth is None:
                    return dummy.next
            group_next = kth.next
            prev, cur = group_next, group_prev.next
            while cur is not group_next:
                nxt = cur.next
                cur.next = prev
                prev, cur = cur, nxt
            old_head = group_prev.next
            group_prev.next = kth
            group_prev = old_head

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;
        while (true) {
            ListNode kth = groupPrev;
            for (int i = 0; i < k; i++) {
                kth = kth.next;
                if (kth == null)
                    return dummy.next;
            }
            ListNode groupNext = kth.next;
            ListNode prev = groupNext, cur = groupPrev.next;
            while (cur != groupNext) {
                ListNode nxt = cur.next;
                cur.next = prev;
                prev = cur; cur = nxt;
            }
            ListNode oldHead = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = oldHead;
        }
    }
}

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* groupPrev = dummy;
        while (true) {
            ListNode* kth = groupPrev;
            for (int i = 0; i < k; i++) {
                kth = kth->next;
                if (kth == nullptr)
                    return dummy->next;
            }
            ListNode* groupNext = kth->next;
            ListNode *prev = groupNext, *cur = groupPrev->next;
            while (cur != groupNext) {
                ListNode* nxt = cur->next;
                cur->next = prev;
                prev = cur; cur = nxt;
            }
            ListNode* oldHead = groupPrev->next;
            groupPrev->next = kth;
            groupPrev = oldHead;
        }
    }
};

func reverseKGroup(head *ListNode, k int) *ListNode {
	dummy := &ListNode{0, head}
	groupPrev := dummy
	for {
		kth := groupPrev
		for range k {
			kth = kth.Next
			if kth == nil {
				return dummy.Next
			}
		}
		groupNext := kth.Next
		prev, cur := groupNext, groupPrev.Next
		for cur != groupNext {
			nxt := cur.Next
			cur.Next = prev
			prev, cur = cur, nxt
		}
		oldHead := groupPrev.Next
		groupPrev.Next = kth
		groupPrev = oldHead
	}
}

var reverseKGroup = function(head, k) {
    const dummy = new ListNode(0, head);
    let groupPrev = dummy;
    while (true) {
        let kth = groupPrev;
        for (let i = 0; i < k; i++) {
            kth = kth.next;
            if (kth === null)
                return dummy.next;
        }
        const groupNext = kth.next;
        let prev = groupNext, cur = groupPrev.next;
        while (cur !== groupNext) {
            const nxt = cur.next;
            cur.next = prev;
            prev = cur; cur = nxt;
        }
        const oldHead = groupPrev.next;
        groupPrev.next = kth;
        groupPrev = oldHead;
    }
};

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    const dummy = new ListNode(0, head);
    let groupPrev: ListNode = dummy;
    while (true) {
        let kth: ListNode | null = groupPrev;
        for (let i = 0; i < k; i++) {
            kth = kth!.next;
            if (kth === null)
                return dummy.next;
        }
        const groupNext: ListNode | null = kth!.next;
        let prev: ListNode | null = groupNext, cur: ListNode | null = groupPrev.next;
        while (cur !== groupNext) {
            const nxt: ListNode | null = cur!.next;
            cur!.next = prev;
            prev = cur; cur = nxt;
        }
        const oldHead: ListNode = groupPrev.next!;
        groupPrev.next = kth;
        groupPrev = oldHead;
    }
};

载入编辑器，自己跑一遍 →

其他解法

两种方法都是 O(n) 时间；递归版结构更简单但占 O(n/k) 栈空间，迭代版需要手动维护组前后的连接，额外空间 O(1)。

解法 2：递归分组反转时间 O(n)，空间 O(n/k)

从 head 向后走 k 步，不足 k 个节点就原样返回 head。否则走到的节点 node 是下一组的开头，先递归处理 node 之后的部分，得到已翻转的剩余链表 prev。再把当前组的 k 个节点逐个头插到 prev 前面，最后返回新的组头。

不需要哑节点和 group_prev，组与组的衔接由返回值自动完成，容易写对。递归深度为组数 n/k，不满足题目进阶要求的 O(1) 额外空间。

import sys

class Solution:
    def reverseKGroup(self, head, k):
        sys.setrecursionlimit(10000)
        node = head
        for _ in range(k):
            if node is None:
                return head
            node = node.next
        prev = self.reverseKGroup(node, k)
        cur = head
        for _ in range(k):
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        return prev

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode node = head;
        for (int i = 0; i < k; i++) {
            if (node == null) return head;
            node = node.next;
        }
        ListNode prev = reverseKGroup(node, k);
        ListNode cur = head;
        for (int i = 0; i < k; i++) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
}

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* node = head;
        for (int i = 0; i < k; i++) {
            if (!node) return head;
            node = node->next;
        }
        ListNode* prev = reverseKGroup(node, k);
        ListNode* cur = head;
        for (int i = 0; i < k; i++) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
};

func reverseKGroup(head *ListNode, k int) *ListNode {
	node := head
	for i := 0; i < k; i++ {
		if node == nil {
			return head
		}
		node = node.Next
	}
	prev := reverseKGroup(node, k)
	cur := head
	for i := 0; i < k; i++ {
		nxt := cur.Next
		cur.Next = prev
		prev, cur = cur, nxt
	}
	return prev
}

var reverseKGroup = function(head, k) {
    let node = head;
    for (let i = 0; i < k; i++) {
        if (!node) return head;
        node = node.next;
    }
    let prev = reverseKGroup(node, k);
    let cur = head;
    for (let i = 0; i < k; i++) {
        const nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
};

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    let node: ListNode | null = head;
    for (let i = 0; i < k; i++) {
        if (!node) return head;
        node = node.next;
    }
    let prev: ListNode | null = reverseKGroup(node, k);
    let cur: ListNode | null = head;
    for (let i = 0; i < k; i++) {
        const nxt: ListNode | null = cur!.next;
        cur!.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

链表专题的其他题目

查看链表全部题目 →