带头结点的单链表就地逆置
时间: 2023-05-30 07:04:04 浏览: 199
线形表---链表---带头节点单链表的就地逆置
3星 · 编辑精心推荐
算法思路:
1. 定义三个指针prev、cur、next,分别指向头结点、头结点的下一个节点和下一个节点的下一个节点。
2. 将头结点的指针域置为NULL,表示反转后的链表末尾节点。
3. 循环遍历单链表,直到cur指向NULL,每次循环,将cur的指针域指向prev,表示将当前节点插入到反转后链表的头部。
4. 将prev指向cur,cur指向next,next指向next的下一个节点,继续遍历单链表。
5. 最后将头结点的指针域指向prev,完成链表的就地反转。
C++代码实现:
```c++
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode *prev = head, *cur = head->next, *next = cur->next;
prev->next = NULL;
while (cur != NULL) {
cur->next = prev;
prev = cur;
cur = next;
if (next != NULL) {
next = next->next;
}
}
head->next = prev;
}
```
阅读全文