剑指offer24：反转链表

题目描述

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

示例:

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

限制

0 <= 节点个数 <= 5000

这道题很经典，直接原地反转就可以。代码的编写可以分为递归和非递归两种。

解法一——非递归

struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};

ListNode* reverseList(ListNode* head)
{
    ListNode* prev=nullptr;
    ListNode* curr=head;
    while(curr)
    {
        ListNode* next=curr->next;
        curr->next=prev;
        prev=curr;
        curr=next;
    }
    return prev;
}

解法二——递归

ListNode* reverseList(ListNode* head)
{
    if(!head||!head->next) return head;
    ListNode* newHead=reverseList(head->next);
    head->next->next=head;
    head->next=nullptr;
    return newHead;
}