Reverse Linked List

Problem

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

Examples

Example 1:

Input: head = [0,1,2,3]

Output: [3,2,1,0]

Example 2:

Input: head = []

Output: []

Constraints

• 0 <= The length of the list <= 1000.
• -1000 <= Node.val <= 1000

You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.

Solution

Increment with prev and current pointers, cache next pointer, set current to point to prev.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        auto current = head;
        ListNode* prev = nullptr;
        while (current) {
            auto next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
};