题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法一：迭代

迭代法应该是我们最容易想到的常规方法，也比较符合人的思维逻辑。其核心思想就是通过两个指针移动，来 一个一个的修改链表的指向方向。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
};

解法二：递归

第二个方法就是使用递归，递归这种方法虽然不太容易能够想到，但是代码却很简洁。

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