题目内容:一个单链表L=(a1 , a2 , … , an-1 , an),其逆单链表定义为L’=( an , an-1 , … , a2 , a1),编写算法将单链表L逆置,要求逆单链表仍占用原单链表的空间。用C语言实现
时间: 2023-08-21 10:05:01 浏览: 52
可以使用三个指针prev、curr、next来逆置单链表L,具体实现如下:
```c
void reverseLinkedList(Node **head) {
Node *prev = NULL;
Node *curr = *head;
Node *next = NULL;
while(curr != NULL) {
next = curr->next; // 保存下一个节点的指针
curr->next = prev; // 当前节点的指针指向前一个节点
prev = curr; // 前一个节点指向当前节点
curr = next; // 当前节点指向下一个节点
}
*head = prev; // 更新头指针
}
```
其中,head是指向链表头节点的指针,Node是链表节点的结构体。```*head = prev```语句将头指针指向原链表的最后一个节点,即逆单链表的第一个节点。
相关问题
逆置单链表。题目描述\n\n题目内容:一个单链表l=(a1 , a2 , … , an-1 , an),其逆单链表定义为l’=( an , an-1 , … , a2 , a1),编写算法将单链表l逆置,
思路:使用三个指针,分别指向当前节点、前一个节点和后一个节点,依次遍历链表,将当前节点的next指向前一个节点,然后将三个指针依次向后移动一个节点,直到遍历完整个链表。
代码实现:
```
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head = pre;
}
```
用C语言表示:一个单链表L=(a1 , a2 , … , an-1 , an),其逆单链表定义为L’=( an , an-1 , … , a2 , a1),编写算法将单链表L逆置,要求逆单链表仍占用原单链表的空间。
以下是用C语言实现将单链表逆置并占用原单链表空间的算法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建单链表
Node* createLinkedList(int n) {
Node* head = NULL;
Node* tail = NULL;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
Node* node = (Node*)malloc(sizeof(Node));
node->data = x;
node->next = NULL;
if (tail == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
return head;
}
// 将单链表逆置
void reverseLinkedList(Node* head) {
if (head == NULL || head->next == NULL) {
return;
}
Node* prev = NULL;
Node* curr = head;
Node* next = head->next;
while (next != NULL) {
curr->next = prev;
prev = curr;
curr = next;
next = next->next;
}
curr->next = prev;
}
// 打印单链表
void printLinkedList(Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
int n;
scanf("%d", &n);
Node* head = createLinkedList(n);
reverseLinkedList(head);
printLinkedList(head);
return 0;
}
```
例如,当输入单链表 1 -> 2 -> 3 -> 4 -> 5 时,程序将输出 5 -> 4 -> 3 -> 2 -> 1。
相关推荐
![](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)