跳转至

206.反转链表 (Easy)*

题目描述*

反转一个单链表。

示例*

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

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

进阶*

可以迭代或递归地反转链表。

代码*

递归*

使用递归函数，一直递归到链表最后一个结点，作为反转后的头结点。

此后返回的过程中，让当前结点的下一个结点的 next 指向当前结点，同时让当前结点的 next 指向 nullptr，实现链表的局部反转。

递归函数全部出栈后，链表反转完成。

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

执行用时：4ms

内存消耗：9.4MB

双指针*

定义两个指针 pre 和 cur，每次让 pre 的 next 指向 cur，实现局部反转。局部反转后，pre 和 cur 同时前移，直到 pre 到达尾部。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = nullptr, *pre = head;
        while(pre != nullptr) {
            ListNode *p = pre->next;
            pre->next = cur;
            cur = pre;
            pre = p;
        }
        return cur;
    }
};

执行用时：8ms

内存消耗：9.2MB

最后更新: July 23, 2022