力扣第 25 題：K 個(gè)一組反轉(zhuǎn)鏈表

題目描述

給定一個(gè)鏈表，將鏈表每k個(gè)節(jié)點(diǎn)一組進(jìn)行反轉(zhuǎn)，并返回修改后的鏈表。如果最后一組節(jié)點(diǎn)數(shù)少于 k，則保持原順序。

• 示例 1：
  • 輸入：1 -> 2 -> 3 -> 4 -> 5，K = 2
  • 輸出：2 -> 1 -> 4 -> 3 -> 5
• 示例 2：
  • 輸入：1 -> 2 -> 3 -> 4 -> 5，K = 3
  • 輸出：3 -> 2 -> 1 -> 4 -> 5

---

解題思路

1. 創(chuàng)建啞節(jié)點(diǎn) dummy，使 dummy->next = head，便于鏈表處理。
2. 使用兩個(gè)指針 prev 和 end 分別標(biāo)記每組要反轉(zhuǎn)的起始和結(jié)束位置。
3. 遍歷鏈表，將每組長(zhǎng)度為 K 的節(jié)點(diǎn)反轉(zhuǎn)；若不足 K 個(gè)則保持原順序。
4. 在反轉(zhuǎn)過(guò)程中，斷開當(dāng)前節(jié)點(diǎn)的 next 指針，保證節(jié)點(diǎn)反轉(zhuǎn)后的正確鏈接。
5. 重復(fù)以上過(guò)程直到鏈表尾部。

---

代碼實(shí)現(xiàn)

#include <stdio.h>
#include <stdlib.h>// 定義鏈表節(jié)點(diǎn)
struct ListNode {int val;struct ListNode *next;
};// 創(chuàng)建新節(jié)點(diǎn)
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 反轉(zhuǎn)鏈表
struct ListNode* reverse(struct ListNode* head, struct ListNode* tail) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr != tail) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}// K 個(gè)一組反轉(zhuǎn)鏈表
struct ListNode* reverseKGroup(struct ListNode* head, int k) {if (k <= 1 || head == NULL) return head;// 創(chuàng)建啞節(jié)點(diǎn)struct ListNode* dummy = createNode(0);dummy->next = head;struct ListNode* prev = dummy;struct ListNode* end = head;while (end != NULL) {// 將 end 指針移動(dòng)到第 k 個(gè)節(jié)點(diǎn)for (int i = 1; i < k && end != NULL; i++) {end = end->next;}if (end == NULL) break;  // 節(jié)點(diǎn)不足 k 個(gè)，跳出循環(huán)struct ListNode* nextGroup = end->next;struct ListNode* start = prev->next;// 斷開鏈表，反轉(zhuǎn)當(dāng)前組end->next = NULL;prev->next = reverse(start, end->next);// 將反轉(zhuǎn)后的鏈表重新連接到下一組start->next = nextGroup;// 移動(dòng) prev 和 end 到下一組起點(diǎn)prev = start;end = prev->next;}struct ListNode* newHead = dummy->next;free(dummy);return newHead;
}// 打印鏈表
void printList(struct ListNode* head) {while (head != NULL) {printf("%d -> ", head->val);head = head->next;}printf("NULL\n");
}// 主函數(shù)測(cè)試
int main() {// 創(chuàng)建鏈表：1 -> 2 -> 3 -> 4 -> 5struct ListNode* head = createNode(1);head->next = createNode(2);head->next->next = createNode(3);head->next->next->next = createNode(4);head->next->next->next->next = createNode(5);printf("原鏈表: ");printList(head);// K 個(gè)一組反轉(zhuǎn)int k = 3;struct ListNode* newHead = reverseKGroup(head, k);printf("K = %d 時(shí)的反轉(zhuǎn)鏈表: ", k);printList(newHead);return 0;
}

---

代碼詳解

1. reverse 函數(shù)

reverse 函數(shù)負(fù)責(zé)反轉(zhuǎn)指定部分鏈表，head 表示要反轉(zhuǎn)的起始節(jié)點(diǎn)，tail 表示結(jié)束節(jié)點(diǎn)。反轉(zhuǎn)后，prev 指向反轉(zhuǎn)后的鏈表開頭。

2. reverseKGroup 函數(shù)

根據(jù) k 的值分組反轉(zhuǎn)鏈表，若最后一組節(jié)點(diǎn)數(shù)量不足 k 則保持原順序。

• prev：記錄每組的前一位置，便于反轉(zhuǎn)后重新連接。
• end：每次向后移動(dòng)到第 k 個(gè)節(jié)點(diǎn)，確定反轉(zhuǎn)的終止位置。
• nextGroup：保存下一組節(jié)點(diǎn)起始位置。

---

圖解流程

以鏈表 1 -> 2 -> 3 -> 4 -> 5、k = 3 為例，代碼運(yùn)行流程如下：

• 初始鏈表：

  1 -> 2 -> 3 -> 4 -> 5
  

• 第一輪反轉(zhuǎn)：

  • 選擇前 3 個(gè)節(jié)點(diǎn)，反轉(zhuǎn)后鏈表變?yōu)?#xff1a;

  3 -> 2 -> 1 -> 4 -> 5
  

• 剩余節(jié)點(diǎn)不足 k 個(gè)：

  • 保持原順序，退出循環(huán)。

最終結(jié)果為 3 -> 2 -> 1 -> 4 -> 5。