题解 | #每K个一组反转链表#

题目链接

每K个一组反转链表

题目描述

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

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

说明：

你需要自行定义链表结构，将输入的数据保存到你的链表中；
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换；
你的算法只能使用常数的额外空间。

解题思路

这个问题要求以 $k$ 个节点为一组，对链表进行分段反转。核心在于分组、反转和链接三个步骤的循环。我们可以使用迭代的方法来解决，这样可以保证空间复杂度为 $\mathcal{O}(1)$ 。

设立哑节点 (Dummy Node)：为了简化对头节点的操作，我们创建一个哑节点 dummy，并让 dummy->next 指向原始链表的头节点 head。最终返回 dummy->next 即可。
分组遍历：我们用一个指针 group_prev 来标记每一组的前驱节点。初始时，group_prev 指向 dummy。我们的目标是反转 group_prev 后面的 $k$ 个节点。
寻找组的末尾：从 group_prev 开始，我们需要向后遍历 $k$ 次，找到当前组的最后一个节点 group_end。
- 如果在遍历过程中提前到达链表末尾（nullptr），则说明剩余的节点不足 $k$ 个，不满足反转条件。此时直接结束整个流程。
执行反转：
- 保存状态：在反转之前，我们需要记录几个关键节点：
  - group_start：当前组的起始节点，即 group_prev->next。
  - next_group_start：下一组的起始节点，即 group_end->next。保存它是为了在当前组反转后能够正确链接到链表的剩余部分。
- 断开与反转：将当前组从主链表中“切”出来，即设置 group_end->next = nullptr。然后，对以 group_start 为头的这个子链表执行一次标准的链表反转。反转后，原来的 group_start 变成了新子链表的尾，而 group_end 变成了新子链表的头。
- 重新链接：
  - 将前一部分 (group_prev) 与反转后的组连接起来：group_prev->next = group_end。
  - 将反转后的组与链表的剩余部分连接起来：group_start->next = next_group_start。
更新指针，进入下一次迭代：
- 当前组操作完成后，它的尾节点（即原来的 group_start）成为了下一组的前驱节点。因此，我们需要更新 group_prev = group_start，然后开始下一轮的分组和反转。

通过循环执行以上步骤，直到链表的剩余部分不足 $k$ 个节点，即可完成整个操作。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <sstream>
#include <string>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 反转一个链表，并返回新的头节点
ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next_temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next_temp;
    }
    return prev;
}

ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head || k == 1) {
        return head;
    }

    ListNode* dummy = new ListNode(0);
    dummy->next = head;

    ListNode* group_prev = dummy;

    while (true) {
        // 1. 寻找 k 个节点，找到 group_end
        ListNode* group_end = group_prev;
        for (int i = 0; i < k; ++i) {
            group_end = group_end->next;
            if (!group_end) { // 剩余节点不足 k 个
                return dummy->next;
            }
        }

        // 2. 保存状态
        ListNode* group_start = group_prev->next;
        ListNode* next_group_start = group_end->next;

        // 3. 断开并反转当前组
        group_end->next = nullptr;
        group_prev->next = reverse(group_start);

        // 4. 重新链接
        group_start->next = next_group_start;
        
        // 5. 更新 group_prev，为下一组做准备
        group_prev = group_start;
    }
    
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr) {
        cout << curr->val << (curr->next ? " " : "");
        curr = curr->next;
    }
    cout << endl;
}

// 辅助函数：从字符串创建链表
ListNode* createList(const string& line) {
    stringstream ss(line);
    int val;
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    while (ss >> val) {
        ListNode* newNode = new ListNode(val);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string line;
    getline(cin, line);
    ListNode* head = createList(line);

    int k;
    cin >> k;

    ListNode* newHead = reverseKGroup(head, k);
    printList(newHead);

    return 0;
}

import java.util.Scanner;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int k = sc.nextInt();

        ListNode head = createList(line);
        ListNode newHead = reverseKGroup(head, k);
        printList(newHead);
    }

    private static ListNode createList(String line) {
        if (line.isEmpty()) {
            return null;
        }
        String[] parts = line.split(" ");
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (String part : parts) {
            current.next = new ListNode(Integer.parseInt(part));
            current = current.next;
        }
        return dummy.next;
    }

    private static void printList(ListNode head) {
        StringBuilder sb = new StringBuilder();
        ListNode current = head;
        while (current != null) {
            sb.append(current.val);
            if (current.next != null) {
                sb.append(" ");
            }
            current = current.next;
        }
        System.out.println(sb.toString());
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode groupPrev = dummy;

        while (true) {
            // 1. 找到 groupEnd
            ListNode groupEnd = groupPrev;
            for (int i = 0; i < k; i++) {
                groupEnd = groupEnd.next;
                if (groupEnd == null) {
                    return dummy.next; // 不足 k 个
                }
            }

            // 2. 保存状态
            ListNode groupStart = groupPrev.next;
            ListNode nextGroupStart = groupEnd.next;

            // 3. 断开并反转
            groupEnd.next = null;
            groupPrev.next = reverse(groupStart);

            // 4. 重新链接
            groupStart.next = nextGroupStart;

            // 5. 更新 groupPrev
            groupPrev = groupStart;
        }
    }
    
    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

import sys

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def reverse(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

def reverse_k_group(head: ListNode, k: int) -> ListNode:
    if not head or k == 1:
        return head
    
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy
    
    while True:
        # 1. 找到 group_end
        group_end = group_prev
        for _ in range(k):
            group_end = group_end.next
            if not group_end:
                return dummy.next # 不足 k 个
        
        # 2. 保存状态
        group_start = group_prev.next
        next_group_start = group_end.next
        
        # 3. 断开并反转
        group_end.next = None
        group_prev.next = reverse(group_start)
        
        # 4. 重新链接
        group_start.next = next_group_start
        
        # 5. 更新 group_prev
        group_prev = group_start

def main():
    try:
        line = sys.stdin.readline().strip()
        if not line: return

        nodes = list(map(int, line.split()))
        k_line = sys.stdin.readline().strip()
        if not k_line: return
        k = int(k_line)

        # 创建链表
        dummy = ListNode(0)
        current = dummy
        for val in nodes:
            current.next = ListNode(val)
            current = current.next
        head = dummy.next
        
        new_head = reverse_k_group(head, k)
        
        # 打印链表
        result = []
        current = new_head
        while current:
            result.append(str(current.val))
            current = current.next
        print(" ".join(result))

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：链表操作、迭代
时间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是链表的节点总数。虽然代码中有一个 while 循环和一个 for 循环，但每个节点只会被访问常数次（一次用于分组检查，一次用于反转）。
空间复杂度： $\mathcal{O}(1)$ 。我们只使用了有限个额外的指针变量来辅助操作，其空间占用与链表的大小无关，满足了题目要求。