剑指offer24:反转链表

2021年3月6日 817点热度 1人点赞 0条评论

题目描述

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

示例:
输入: 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;
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

您需要 登录 之后才可以评论