K个一组翻转链表的解题策略

“K 个一组翻转链表”的问题是关于链表操作的算法题，要求对链表中的节点按照每 k 个一组进行翻转，翻转后保持链表的结构，若剩余节点不足 k 个，则保持原样。题目还提出了两个进阶条件：一是算法应使用常数额外空间，二是不能仅改变节点值，而是要进行实际的节点交换。 该问题的关键在于如何高效地找到每 k 个节点的边界并完成翻转。一个可能的解决方案是采用迭代的方式，利用双指针维护当前处理的 k 个节点范围。首先创建一个虚拟头节点 `hair`，使其指向链表的真正头节点，这样方便后续处理。然后定义两个指针 `pre` 和 `head` 分别表示当前 k 个节点的起点和终点，初始化时 `pre = hair`，`head = hair->next`。 在每次循环中，首先检查 `head` 是否已经到达链表尾部，如果是，则结束翻转；如果不是，就寻找第 k 个节点，将其设为 `tail`。接着调用辅助函数 `myReverse` 来翻转 `head` 到 `tail` 之间的子链表，这个函数会返回翻转后的新头和新尾。更新 `pre->next` 指向翻转后的新头，然后将 `pre` 移动到 `tail` 的位置，`head` 移动到 `tail->next`，继续寻找下一个 k 个节点的范围。这个过程会一直持续到 `head` 达到链表尾部。 在 `myReverse` 函数中，通过迭代遍历子链表，每次将 `p->next` 指向 `prev`，依次更新 `p`、`prev` 和 `next`，直到 `p` 和 `prev` 相遇，此时子链表已翻转，返回新的头和尾。 在题目提供的参考代码中，使用 C++ 实现了这个思路，具体代码如下： ```cpp class Solution { public: // 翻转一个子链表，并且返回新的头与尾 pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) { ListNode* prev = tail->next; ListNode* p = head; while (prev != tail) { ListNode* nex = p->next; p->next = prev; prev = p; p = nex; } return {tail, head}; } ListNode* reverseKGroup(ListNode* head, int k) { ListNode* hair = new ListNode(0); hair->next = head; ListNode* pre = hair; while (head) { // ... (其余代码省略) } } }; ``` 这个算法的时间复杂度是 O(n)，其中 n 是链表的节点数量，因为它只遍历链表一次。空间复杂度是 O(1)，因为只使用了常数级别的额外空间。满足了题目的进阶要求。