设计算法将单链表L就地逆置,即利用原表各结点的空间实现逆置。
时间: 2023-12-03 21:44:15 浏览: 140
写一个算法将一单链表逆置。要求操作在原链表上进行。
可以使用三个指针来实现单链表的就地逆置,具体算法如下:
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指向的就是逆置后的尾结点。
阅读全文