网站制作公司官网首页,撸撸撸做最好的导航网站,wordpress贴心插件,如何做网站宣传自己目录
1.创建一个链表
1.链表节点定义
2.创建新节点
3.链表生成#xff08;输入#xff09;
4.链表输出
2.链表指定区间反转函数
1.创建哑节点
2.找到第m-1位的节点#xff0c;开始 反转
3.连接反转后的链表与未反转的链表
3.未使用哑节点的运行结果
这段代码可以…目录
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-NULLm2n4
1.创建哑节点
问题处理 m1 的特殊情况
当要从头节点开始反转m1时 反转后头节点会改变原第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
