AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

206. 反转链表

作者: 作者的头像   枳花明 ,  2025-05-09 09:48:54 · 北京 ,  所有人可见 ,  阅读 2


0


简单理解:
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

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息