实现单链表的原地置逆
时间: 2024-06-10 20:09:36 浏览: 2
单链表的原地置逆可以通过改变节点之间的指针关系来实现。具体步骤如下:
1. 定义三个指针pre、curr和next,分别指向当前节点的前一个节点、当前节点和当前节点的下一个节点。
2. 初始化pre为NULL,curr为pHead。
3. 遍历链表,直到curr为空。
- 先将next指针指向curr的下一个节点,以防止链表断裂。
- 将curr的下一个节点指向pre,完成节点的指针反转。
- 将pre指向curr,curr指向next,继续下一轮遍历。
4. 遍历结束后,将pHead指向pre,作为链表的新头节点。
5. 返回新链表的头节点pHead。
相关问题
借助堆栈将一个单链表置逆
借助堆栈将一个单链表置逆的基本思路如下:
1. 遍历单链表,将每个节点依次压入栈中。
2. 弹出栈中的节点,重新构造一个新的单链表。
下面是示例代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* reverseList(ListNode* head) {
if (head == NULL) {
return NULL;
}
ListNode *p = head;
ListNode *newHead = NULL;
ListNode *temp = NULL;
// 创建一个堆栈
ListNode **stack = (ListNode **)malloc(sizeof(ListNode *) * 1000);
int top = -1;
// 将链表中的节点压入堆栈中
while (p != NULL) {
stack[++top] = p;
p = p->next;
}
// 弹出堆栈中的节点,重新构造一个新的链表
newHead = stack[top--];
temp = newHead;
while (top >= 0) {
temp->next = stack[top--];
temp = temp->next;
}
temp->next = NULL;
free(stack);
return newHead;
}
int main() {
// 创建一个链表 1->2->3->4->5
ListNode *head = (ListNode *)malloc(sizeof(ListNode));
head->val = 1;
head->next = NULL;
ListNode *p = head;
for (int i = 2; i <= 5; i++) {
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->val = i;
node->next = NULL;
p->next = node;
p = p->next;
}
// 输出原始链表
printf("Original list: ");
p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
// 翻转链表
head = reverseList(head);
// 输出翻转后的链表
printf("Reversed list: ");
p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
return 0;
}
```
c语言单链表原地逆置
你可以使用迭代或递归的方式来实现单链表的原地逆置。下面是使用迭代方式的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct Node {
int data;
struct Node* next;
};
// 原地逆置单链表
struct Node* reverseList(struct Node* head) {
struct Node *prev = NULL;
struct Node *curr = head;
struct Node *next = NULL;
while (curr != NULL) {
next = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 当前节点指向前一个节点
prev = curr; // 更新前一个节点为当前节点
curr = next; // 更新当前节点为下一个节点
}
return prev; // 返回逆置后的头节点
}
// 打印链表
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
// 创建链表
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
struct Node* fourth = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = fourth;
fourth->data = 4;
fourth->next = NULL;
printf("原链表:");
printList(head);
// 逆置链表
head = reverseList(head);
printf("逆置后的链表:");
printList(head);
return 0;
}
```
这段代码首先定义了一个单链表节点结构体 `Node`,包含一个整型数据 `data` 和指向下一个节点的指针 `next`。然后,定义了 `reverseList` 函数,通过迭代的方式实现了单链表的原地逆置。最后,在 `main` 函数中创建了一个简单的链表,并调用 `reverseList` 函数进行逆置,打印出逆置后的结果。
希望能帮到你!如果有任何疑问,请随时提问。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)