AcWing 35. 反转链表
原题链接
简单
作者:
Lxxx_6
,
2021-02-01 11:04:00
,
所有人可见
,
阅读 456
翻转链表 WriteUp
原题链接
ACwing原题链接!!!
AC 源代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL; //pre相当于是答案,由于链表最后一个元素为NULL,因此翻转之后第一个元素为NULL,那么答案就从NULL开始
auto cur = head; //cur用来遍历链表
while ( cur != NULL)
{
auto tmp = cur->next; //tmp为临时变量
cur->next = pre; //把cur的下一个指针指向pre,相当于添加了一个答案
pre = cur; //把pre往后移动一位
cur = tmp; //恢复cur原本的位置
}
return pre;
}
};
算法思路
- 新建一个空元素叫做pre,值为NULL(pre相当于是答案,由于链表最后一个元素为NULL,因此翻转之后第一个元素为NULL,那么答案就从NULL开始)
- cur用来从head遍历链表
- 新建一个tmp临时变量保存cur
- 把cur的下一个指针指向pre,相当于向pre中添加了一个答案
- 把pre往后移动一位
- cur=tmp,恢复cur原本的位置
参考资料
B站UP主滚滚的讲解,很生动!!!!