C語言——鏈表指定區間反轉

1.創建一個鏈表

1.鏈表節點定義

2.創建新節點

3.鏈表生成（輸入）

4.鏈表輸出

2.鏈表指定區間反轉函數

1.創建啞節點

2.找到第m-1位的節點，開始?反轉

3.連接反轉后的鏈表與未反轉的鏈表

3.未使用啞節點的運行結果

這段代碼可以直接運行檢測結果

1.創建一個鏈表

1.鏈表節點定義

#include <stdio.h>
#include <stdlib.h>// 鏈表節點定義
struct ListNode {int val;struct ListNode* next;
};

2.創建新節點

// 創建新節點
struct ListNode* createNode(int value) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));if (newNode == NULL) {printf("內存分配失敗!\n");exit(1);}newNode->val = value;newNode->next = NULL;return newNode;
}

3.鏈表生成（輸入）

// 從數組創建鏈表
struct ListNode* createListFromArray(int arr[], int size) {if (size == 0) return NULL;struct ListNode* head = createNode(arr[0]);struct ListNode* current = head;for (int i = 1; i < size; i++) {current->next = createNode(arr[i]);current = current->next;}return head;
}// 交互式輸入創建鏈表
struct ListNode* createListInteractive() {int n, value;printf("請輸入鏈表節點個數: ");scanf("%d", &n);if (n <= 0) return NULL;printf("請輸入%d個節點的值:\n", n);scanf("%d", &value);struct ListNode* head = createNode(value);struct ListNode* current = head;for (int i = 1; i < n; i++) {scanf("%d", &value);current->next = createNode(value);current = current->next;}return head;
}

4.鏈表輸出

// 打印鏈表
void printList(struct ListNode* head) {struct ListNode* current = head;printf("鏈表: ");while (current != NULL) {printf("%d", current->val);if (current->next != NULL) {printf(" → ");}current = current->next;}printf(" → NULL\n");
}// 帶詳細信息的打印
void printListDetailed(struct ListNode* head) {struct ListNode* current = head;int count = 1;printf("鏈表詳細信息:\n");printf("地址       值   下一個節點\n");printf("-------------------------\n");while (current != NULL) {printf("%p  %2d  ", (void*)current, current->val);if (current->next != NULL) {printf("%p", (void*)current->next);} else {printf("NULL");}printf("\n");current = current->next;count++;}printf("-------------------------\n");
}

2.鏈表指定區間反轉函數

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {if (head == NULL || m == n) return head;// 創建啞節點 - 關鍵步驟！struct ListNode dummy;dummy.next = head;struct ListNode* pre = &dummy;// 移動到第 m-1 個節點for (int i = 1; i < m; i++) {pre = pre->next;}// 反轉 m 到 n 的節點struct ListNode* cur = pre->next;struct ListNode* next = NULL;struct ListNode* prev = NULL;for (int i = m; i <= n; i++) {next = cur->next;cur->next = prev;prev = cur;cur = next;}// 重新連接鏈表pre->next->next = cur;  // 新尾節點連接后繼pre->next = prev;       // 前驅連接新頭節點return dummy.next;  // 返回真正的頭節點
}

解釋一下實現過程：演示鏈表為1->2->3->4->5->NULL，m=2，n=4

1.創建啞節點

問題：處理 m=1 的特殊情況

當要從頭節點開始反轉（m=1）時：

反轉后頭節點會改變（原第n個節點成為新頭）
如果沒有啞節點，需要特殊處理這種情況

2.找到第m-1位的節點，開始?反轉

for (int i = 1; i < m; i++) {pre = pre->next;
}

dummy → 1 → 2 → 3 → 4 → 5 → NULL↑pre (指向節點1)

3.連接反轉后的鏈表與未反轉的鏈表

未進行連接時（僅反轉）

dummy → 1 → 2 ← 3 ← 4    5 → NULL↑          ↑    ↑pre        prev cur
反轉部分：4 → 3 → 2 → NULL

進行連接后

dummy → 1 → 4 → 3 → 2 → 5 → NULL↑    ↑    ↑    ↑    ↑pre  新頭  中間  新尾 cur

3.未使用啞節點的運行結果

我們將返回的啞節點改成head，就將會返回未使用啞節點的反轉鏈表的頭結點。

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {if (head == NULL || m == n) return head;// 創建啞節點 - 關鍵步驟！struct ListNode dummy;dummy.next = head;struct ListNode* pre = &dummy;// 移動到第 m-1 個節點for (int i = 1; i < m; i++) {pre = pre->next;}// 反轉 m 到 n 的節點struct ListNode* cur = pre->next;struct ListNode* next = NULL;struct ListNode* prev = NULL;for (int i = m; i <= n; i++) {next = cur->next;cur->next = prev;prev = cur;cur = next;}// 重新連接鏈表pre->next->next = cur;  // 新尾節點連接后繼pre->next = prev;       // 前驅連接新頭節點return head;  // 返回
}

使用啞節點

這段代碼可以直接運行檢測結果

#include <stdio.h>
#include <stdlib.h>// 鏈表節點定義
struct ListNode {int val;struct ListNode* next;
};
// 創建新節點
struct ListNode* createNode(int value) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));if (newNode == NULL) {printf("內存分配失敗!\n");exit(1);}newNode->val = value;newNode->next = NULL;return newNode;
}
// 從數組創建鏈表
struct ListNode* createListFromArray(int arr[], int size) {if (size == 0) return NULL;struct ListNode* head = createNode(arr[0]);struct ListNode* current = head;for (int i = 1; i < size; i++) {current->next = createNode(arr[i]);current = current->next;}return head;
}// 交互式輸入創建鏈表
struct ListNode* createListInteractive() {int n, value;printf("請輸入鏈表節點個數: ");scanf("%d", &n);if (n <= 0) return NULL;printf("請輸入%d個節點的值:\n", n);scanf("%d", &value);struct ListNode* head = createNode(value);struct ListNode* current = head;for (int i = 1; i < n; i++) {scanf("%d", &value);current->next = createNode(value);current = current->next;}return head;
}
// 打印鏈表
void printList(struct ListNode* head) {struct ListNode* current = head;printf("鏈表: ");while (current != NULL) {printf("%d", current->val);if (current->next != NULL) {printf(" → ");}current = current->next;}printf(" → NULL\n");
}// 帶詳細信息的打印
void printListDetailed(struct ListNode* head) {struct ListNode* current = head;int count = 1;printf("鏈表詳細信息:\n");printf("地址       值   下一個節點\n");printf("-------------------------\n");while (current != NULL) {printf("%p  %2d  ", (void*)current, current->val);if (current->next != NULL) {printf("%p", (void*)current->next);} else {printf("NULL");}printf("\n");current = current->next;count++;}printf("-------------------------\n");
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {if (head == NULL || m == n) return head;// 創建啞節點 - 關鍵步驟！struct ListNode dummy;dummy.next = head;struct ListNode* pre = &dummy;// 移動到第 m-1 個節點for (int i = 1; i < m; i++) {pre = pre->next;}// 反轉 m 到 n 的節點struct ListNode* cur = pre->next;struct ListNode* next = NULL;struct ListNode* prev = NULL;for (int i = m; i <= n; i++) {next = cur->next;cur->next = prev;prev = cur;cur = next;}// 重新連接鏈表pre->next->next = cur;  // 新尾節點連接后繼pre->next = prev;       // 前驅連接新頭節點return dummy.next;  // 返回真正的頭節點
}
// 釋放鏈表內存
void freeList(struct ListNode* head) {struct ListNode* current = head;while (current != NULL) {struct ListNode* temp = current;current = current->next;free(temp);}
}int main() {// 方法1: 從數組創建鏈表int arr[] = {1, 2, 3, 4, 5};int size = sizeof(arr) / sizeof(arr[0]);struct ListNode* head = createListFromArray(arr, size);printf("從數組創建的鏈表:\n");printList(head);printListDetailed(head);// 方法2: 交互式輸入創建鏈表/*struct ListNode* head2 = createListInteractive();printf("交互式輸入的鏈表:\n");printList(head2);freeList(head2);*/// 測試區間反轉int m = 1, n = 4;printf("\n反轉區間 [%d, %d] 后的鏈表:\n", m, n);// 這里可以調用你的reverseBetween函數head = reverseBetween(head, m, n);printList(head);// 釋放內存freeList(head);return 0;
}

運行結果

~/gpt-vue_191657 gcc linkedlist.c -o linkedlist && ./linkedlist
從數組創建的鏈表:
鏈表: 1 → 2 → 3 → 4 → 5 → NULL
鏈表詳細信息:
地址       值   下一個節點
-------------------------
0x557bae1cc2a0   1  0x557bae1cc2c0
0x557bae1cc2c0   2  0x557bae1cc2e0
0x557bae1cc2e0   3  0x557bae1cc300
0x557bae1cc300   4  0x557bae1cc320
0x557bae1cc320   5  NULL
-------------------------反轉區間 [1, 4] 后的鏈表:
鏈表: 4 → 3 → 2 → 1 → 5 → NULL

反轉函數返回值換為head后，運行結果：

~/gpt-vue_191657 gcc linkedlist_modified.c -o linkedlist_modified && ./linkedlist_modified
從數組創建的鏈表:
鏈表: 1 → 2 → 3 → 4 → 5 → NULL
鏈表詳細信息:
地址       值   下一個節點
-------------------------
0x560fb96ca2a0   1  0x560fb96ca2c0
0x560fb96ca2c0   2  0x560fb96ca2e0
0x560fb96ca2e0   3  0x560fb96ca300
0x560fb96ca300   4  0x560fb96ca320
0x560fb96ca320   5  NULL
-------------------------反轉區間 [1, 4] 后的鏈表:
鏈表: 1 → 5 → NULL