题目描述

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

样例

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

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

算法思路

思路概括如下：
1. 定义一个新的头节点
2. 暂存原始头节点的下一个节点
3. 原始头的下一个节点赋值为新头
4. 新头再指向原始头
5. 原始头指向暂存的下一个节点

这样就完成了一次翻转

C++ 代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *new_head = NULL;
        while(head != NULL) {
            ListNode *next = head->next;
            head -> next = new_head;
            new_head = head;
            head = next;
        }
        return new_head;
    }
};