algoadvance

Leetcode 206. Reverse Linked List

Problem Statement

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

Clarifying Questions

  1. What type of data does the linked list store? - The linked list stores integers.
  2. Is the input list guaranteed to be non-null? - No, the list can be empty (i.e., the head can be nullptr).
  3. Should we modify the original list or create a new reversed list? - We should reverse the list in place.
  4. Are there any constraints on the length of the linked list? - No explicit constraints, but typical constraints from the problem’s environment apply, e.g., memory and stack size.

Strategy

To reverse the linked list iteratively:

  1. Initialize three pointers: prev, curr, and next.
  2. Traverse through the linked list. For each node, adjust its next pointer to point to the previous node (prev).
  3. Move the pointers one step forward repeatedly until all the nodes have been reversed.
  4. Finally, return the new head of the reversed list, which is the last non-null node encountered.

Code

Here’s the implementation in C++:

/**
 * 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) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            // Store the next node
            ListNode* nextTemp = curr->next;
            // Reverse the current node's pointer
            curr->next = prev;
            // Move pointers one step forward
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. We traverse each node exactly once.

The space complexity is O(1) since we are using a constant number of extra pointers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI