设计一个算法,通过遍历一趟,将链表中所有结点逆置,仍利用原表的存储空间。
时间: 2023-04-17 13:02:18 浏览: 74
算法步骤如下:
1. 定义三个指针:pre、cur、next,分别指向当前结点的前一个结点、当前结点和当前结点的后一个结点。
2. 初始化pre为NULL,cur为链表的头结点。
3. 遍历链表,每次将cur的next指针指向pre,然后将pre、cur、next分别向后移动一个结点,直到遍历完整个链表。
4. 最后将链表的头结点指向pre,完成链表的逆置。
代码实现如下:
void reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head = pre;
}
相关问题
设计一个算法,将一个带头结点的单链表的所有结点逆置。
算法如下:
1. 定义三个指针:pre、cur、next,分别指向当前结点的前一个结点、当前结点和当前结点的后一个结点。
2. 将 cur 指向头结点的下一个结点,pre 指向头结点,next 指向 cur 的下一个结点。
3. 循环遍历链表,每次将 cur 的 next 指向 pre,然后将 pre、cur、next 分别向后移动一个结点。
4. 当 cur 指向 null 时,说明链表已经遍历完毕,此时将头结点的 next 指向 pre,完成链表的逆置。
代码实现如下:
```
void reverseList(ListNode* head) {
ListNode* pre = head;
ListNode* cur = head->next;
ListNode* next = cur->next;
pre->next = nullptr;
while (cur != nullptr) {
cur->next = pre;
pre = cur;
cur = next;
if (next != nullptr) {
next = next->next;
}
}
head->next = pre;
}
```
设计算法将单链表L就地逆置,即利用原表各结点的空间实现逆置。
可以使用三个指针来实现单链表的就地逆置,具体算法如下:
1. 初始化三个指针:pre指向NULL,cur指向L的头结点,next指向cur的下一个结点。
2. 遍历链表,依次将cur结点的next指向pre结点,然后将pre、cur、next分别后移。具体操作如下:
a. 将cur的next指向pre:cur->next = pre;
b. 将pre、cur、next依次向后移动:pre = cur; cur = next; next = next->next;
3. 遍历完链表后,将原链表的头结点指向逆置后的尾结点。具体操作如下:
a. 将L的头结点指向pre结点:L->next = pre;
最后返回L即可。
下面是C++代码实现:
```c++
void reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head->next;
ListNode* next = cur->next;
while (next != NULL) {
cur->next = pre;
pre = cur;
cur = next;
next = next->next;
}
cur->next = pre;
head->next = cur;
}
```
需要注意的是,这里的head是一个头结点,而不是实际存储数据的第一个结点。在遍历完链表后,head->next指向的就是逆置后的尾结点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)