简单理解:
pre
逐步“追赶”到反转链表的新头部。
cur
逐个节点“被处理”到链表的尾部。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr; // 代表已经反转部分的链表的尾部,也就是“已处理”部分的前一个节点。
ListNode* cur = head; // 当前正在处理的节点
while( cur )
{
ListNode* nxt = cur->next; // 保存cur->next,以避免断链
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};
原始链表: 1 -> 2 -> 3 -> 4 -> 5
初始状态:
pre = nullptr
cur = 1
循环1:
保存 nxt = 2
1->next 设为 pre( nullptr)
pre = 1
cur = 2
状态:
pre: 1 -> nullptr
cur: 2 -> 3 -> 4 -> 5
循环2:
nxt = 3
2->next = pre (1)
pre = 2
cur = 3
状态:
pre: 2 -> 1 -> nullptr
cur: 3 -> 4 -> 5
循环3:
nxt = 4
3->next = pre (2)
pre = 3
cur = 4
状态:
pre: 3 -> 2 -> 1 -> nullptr
cur: 4 -> 5
循环4:
nxt = 5
4->next = pre (3)
pre = 4
cur = 5
状态:
pre: 4 -> 3 -> 2 -> 1 -> nullptr
cur: 5
最后:
nxt = nullptr
5->next = pre (4)
pre = 5
cur = nullptr
反转完毕,头节点为 pre(5):
5 -> 4 -> 3 -> 2 -> 1 -> nullptr