一个单链表L=(a1 , a2 , … , an-1 , an),其逆单链表定义为L’=( an , an-1 , … , a2 , a1),编写算法将单链表L逆置,要求逆单链表仍占用原单链表的空间。
时间: 2024-05-01 11:19:21 浏览: 21
可以使用三个指针来实现单链表的逆置,具体步骤如下:
1. 令p指向单链表的第一个节点,q指向第二个节点,r指向第三个节点;
2. 将p的next指针指向NULL;
3. 将q的next指针指向p;
4. 将r的next指针指向q;
5. 依次将q、r指针往后移动一个节点,直到r指向最后一个节点,即NULL;
6. 将原单链表的头节点指向逆置后的最后一个节点。
具体的代码实现如下:
```
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* p = head;
ListNode* q = head->next;
ListNode* r = q->next;
p->next = NULL;
while (r != NULL) {
q->next = p;
p = q;
q = r;
r = r->next;
}
q->next = p;
head = q;
}
```
需要注意的是,如果原单链表为空或只有一个节点,则无需逆置,直接返回即可。同时,逆置后需要更新原单链表的头节点指针。
相关问题
一个单链表l=(a1 , a2 , … , an-1 , an),其逆单链表定义为l’=( an , an-1 , … , a2 , a1),编写算法将单链表l逆置,要求逆单链表仍占用原单链表的空间。
可以使用三个指针来实现单链表的逆置。具体步骤如下:
1. 定义三个指针pre、cur、nex,初始时pre指向null,cur指向单链表的头节点,nex指向cur的下一个节点。
2. 遍历单链表,循环执行以下操作:
- 将cur的next指针指向pre,实现逆置。
- 将pre指针移动到cur,cur指针移动到nex,nex指针移动到nex的下一个节点。
3. 遍历结束后,cur指针指向单链表的尾节点,将其设置为新的头节点。
算法如下:
```
Node* reverseList(Node* head) {
Node* pre = nullptr;
Node* cur = head;
Node* nex = nullptr;
while (cur != nullptr) {
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
return pre;
}
```
需要注意的是,这种方法修改了单链表中每个节点的next指针,并且需要额外空间存储pre和nex指针。
用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。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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)