206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

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

// Iteration
ListNode* reverseList(ListNode* head) { // time: O(n); space: O(1)
    ListNode *pre = nullptr, *cur = head, *nex = nullptr;
    while (cur) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    return pre;
}

// Recursion
ListNode* reverseList(ListNode* head) { // time: O(n); space: O(n)
    if (!head || !head->next) return head;
    ListNode* node = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return node;
}

92. Reverse Linked List II