206

206. Reverse Linked List (Easy)

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

 

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Companies:
Microsoft, Bloomberg, Amazon, Facebook, Apple, Nvidia, Google, Yandex, Adobe, eBay, IBM

Related Topics:
Linked List, Recursion

Similar Questions:

• Reverse Linked List II (Medium)
• Binary Tree Upside Down (Medium)
• Palindrome Linked List (Easy)
• Reverse Nodes in Even Length Groups (Medium)

Solution 1. Iterative

// OJ: https://leetcode.com/problems/reverse-linked-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode h;
        while (head) {
            auto p = head;
            head = head->next;
            p->next = h.next;
            h.next = p;
        }
        return h.next;
    }
};

Solution 2. Recursive

// OJ: https://leetcode.com/problems/reverse-linked-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
    array<ListNode*, 2> reverse(ListNode *head) {
        if (!head->next) return {head, head};
        auto [h, t] = reverse(head->next);
        t->next = head;
        head->next = NULL;
        return {h, head};
    }
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return NULL;
        return reverse(head)[0];
    }
};