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.
-
n
-
Node.value
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:
-
Initialize three pointers:
previous
,nextNode
, andcurrent
. Theprevious
andnextNode
pointers are initialized as NULL, while thecurrent
pointer is initialized to the head of the linked list. -
Iterate over the linked list. While iterating, perform the following steps:
- Before changing the
next
pointer ofcurrent
, store the next node innextNode
to prevent losing the reference to the rest of the list. - Update the
next
pointer ofcurrent
to point to theprevious
node. This effectively reverses the pointer of the current node. - Move
previous
tocurrent
andcurrent
tonextNode
to move to the next iteration.
- Before changing the
-
After reversing the whole linked list, we’ll change the head pointer to the
previous
pointer becauseprevious
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.