面试必刷TOP101

题目来源

牛客/题库/在线编程/算法篇/面试必刷TOP101

链表

BM1 反转链表

题目

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

示例

输入：{1,2,3}
返回值：{3,2,1}

输入：{}
返回值：{}

代码

/**
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
#include <cstdio>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        // write code here
        ListNode* res = nullptr;//存储节点
        ListNode* temp = nullptr;//临时保存要操作的链表后续地址，防止断开后找不到节点入口遍历
        ListNode* cur = head;//遍历指针
        while (cur!=nullptr) {//当遍历指针为空时，则不需要进行操作说明已经反转好了，循环条件为!=nullptr
            temp = cur->next;//记录下待反转链表的入口地址以便提供给下一次遍历指针
            cur->next = res;//断开cur->next指针指向res反转链表
            res = cur;//后移反转链表指针
            cur = temp;//cur开始遍历下一个节点
        }
        return res;//最后返回反转链表指针
    }
};