Solution: Reverse Linked List II
Let's solve the Reverse Linked List II problem using the In-Place Manipulation of a Linked List pattern.
Statement
Given a singly linked list with nodes and two positions, left
and right
, the objective is to reverse the nodes of the list from left
to right
. Return the modified list.
Constraints:
-
n
-
node.data
-
left
right
n
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.
Naive approach
The naive approach uses two pointers left
and right
to keep track of the sublist and reverse it. The pointers left
and right
are intialized to the head of the linked list.
We begin by moving the left
pointer to the node, that represents the start of the sublist and the right
pointer to the node, that represents the end of the sublist. Next, while the left
pointer is behind the right
pointer, we take the following steps:
-
We swap the values of the nodes pointed to by the
left
and theright
pointer. -
We move the
left
pointer one step forward to the node. -
Since we are given a singly linked list, and there is no
prev
, we can’t update theright
pointer in the same way as we did for theleft
pointer, i.e., moving it backward to the node. Instead, on each iteration, we reset theright
pointer to the head of the list and then move it forward to the node. -
We repeat steps 1–3 until both pointers meet at some point, or the
right
crossesleft
.
The time complexity of this solution is , since we’re swapping the nodes, and traversing the list per iteration. The space complexity of this solution , since we use a constant number of extra variables.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.