AcWing 35. 反转链表

题目

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

思考题：

• 请同时实现迭代版本和递归版本。

数据范围

链表长度 。

样例

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

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

题解

递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head -> next) return head;
        auto res = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return res;
    }
};

迭代

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