设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间
时间: 2023-04-22 17:01:09 浏览: 103
03016202万玥汝第一次实验报告_单链表逆转_单链表后插入新节点_删除结点_查找结点_
可以使用三个指针来实现链表的反转,分别为当前节点指针cur、前驱节点指针pre和后继节点指针next。具体步骤如下:
1. 将当前节点指针cur指向链表的头节点。
2. 遍历链表,当cur指针不为空时,执行以下操作:
a. 将后继节点指针next指向cur的下一个节点。
b. 将cur的下一个节点指向前驱节点pre。
c. 将前驱节点指针pre指向当前节点cur。
d. 将当前节点指针cur指向后继节点指针next。
3. 遍历结束后,将链表的头节点指向前驱节点pre,即可完成链表的反转。
代码实现如下:
```
void reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = nullptr;
ListNode* next = nullptr;
while (cur != nullptr) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head = pre;
}
```
阅读全文