206.反转链表.md

206.反转链表

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

 

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

 

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

 

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

标签：

['递归', '链表']

难度：Easy

喜欢：2665

---

迭代

时间复杂度

$O(n)$

代码实现

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

参考文献

递归

算法思路

时间复杂度

$O(n)$

代码实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL ) return head;
        ListNode* tail = reverseList(head->next); // head->next的反转结果，返回链表头
        head->next->next = head; // 头部两个元素进行反转
        head->next = NULL;
        return tail;
    }
};

参考文献