Solution: Reverse Linked List

Let’s solve the Reverse Linked List problem.

We'll cover the following

Statement

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

Constraints:

Let n be the number of nodes in a linked list.

  • 1≤1 \leq n ≤5×102\leq 5\times10^2
  • −5×103≤-5\times10^3 \leq Node.value ≤5×103\leq 5\times10^3

Solution

We will reverse the linked list without using any additional data structures by keeping track of the current, next, and previous nodes. By maintaining references to these nodes, we can iteratively traverse the linked list, updating the references as needed to reverse the order of the elements. This approach ensures that each node’s reference is correctly adjusted to point to its previous node, effectively reversing the linked list.

To reverse the linked list, we will follow these steps:

  1. Initialize three pointers: previous, next_node, and current. The previous and next_node pointers are initialized as NULL, while the current pointer is initialized to the head of the linked list.

  2. Iterate over the linked list. While iterating, perform the following steps:

    • Before changing the next pointer of current, store the next node in next_node to prevent losing the reference to the rest of the list.
    • Update the next pointer of current to point to the previous node. This effectively reverses the pointer of the current node.
    • Move previous to current and current to next_node to move to the next iteration.

  3. After reversing the whole linked list, we’ll change the head pointer to the previous pointer because previous will be pointing to the new head node.

Let’s look at the following illustration to get a better understanding of reversing the linked list:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.