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