题目描述

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

样例

输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

C++ 代码

/**
 * 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) {
        if(!head || !head->next)  return head;  // 说明nullptr 或者只有一个节点， 不需要反转

        // 这里最后一步返回的是 5(tail) 此时的head->next = 4  最后一步是将 4 ->5->nullptr 转化为 5-> 4 -> nullptr;
        auto re = reverseList(head->next);   // 进行一个递归， 返回的是反转链表的头结点  

        // 由上面的就需要做下面的步骤
        head->next->next = head;    // 将5 作为头结点
        head->next = nullptr;       // 


        // 理解
        // 1 -> 2 -> 3 -> 4 -> 5 ->null
        // 最开始的递归此时的head->next = 2,是直接返回的head 的next节点反转的情况, 后面的返回成功的话，就是下面的结果
        // 此时别的节点不动， head = 1 (在原点不动)， head->next (已经反转到新链表尾部， 这时候应该1 还是指向2的)
        // 1 、 5 -> 4 -> 3 -> 2 ->null   (1 ->next = 2)

        // 所以现在只需要将 head->next(2)->next = head(1)  将1 放在2的后面 然后将head(1) ->next = nullptr 即可
        // 就变成 5 -> 4 -> 3 -> 2 -> 1 ->null

        // 然后进行一系列的分析： 
        // 第一次应该是5 -> 4 -> null  此时head 是 3, head->next（4） head->next(4)->next = head(3) 
        // 

        return re;
    }
};

C++ 代码

/**
 * 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 = nullptr;        // 作为记录节点的前驱节点
        auto cur = head;                // 作为当前节点
        while(cur)                  // cur节点一直执行到最后一个nullptr 结束
        {
            auto next = cur->next;   // 保存当前节点的下一个节点
            cur->next = pre;        // 修改当前节点的指针， 反向
            pre = cur;          // pre   向后移位
            cur = next;         // cur 节点向后， 一直可以到nullptr

        }
        return pre;     // 返回的是nullptr 的前一个节点最为head节点
    }
};