The in-place reversal of a linked list pattern allows us to reverse a linked list without any additional memory, using only the given nodes.
Many problems require a reversal of a set of nodes in a linked list without using additional memory. In such cases, using the in-place reversal pattern is the simplest solution. Instead of making a new linked list with reversed links, we can do it in place, without using additional memory.
We iterate in a linked list and keep track of the current node, the next node, and the previous node simultaneously.
The naive approach of iterating the linked list using nested loops takes O(n*2) time, requires the use of additional memory. Using the in-place reversal pattern, the time complexity is O(n) time, only O(1)O(1) space, since we use a single loop to iterate the linked list.
There are 4 steps in one movement:
let nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
There are some problems can be solved with this approach
- Remove the Nth node from end of list
- Reverse the alternate nodes and append them at the end of the list
- Reverse the second half of the linked list
- Reverse Nodes in k-Group
- Swapping Nodes in a Linked List
#206 Given the head
of a singly linked list, reverse the list, and return the reversed list.
var reverseList = function(head) {
let prev = null;
let cur = head;
while(cur) {
// destructuring assignment
[cur.next, prev, cur] = [prev, cur, cur.next];
}
return prev;
};
Reverse Nodes in k-Group #25
Given the head of a linked list, reverse the nodes of the list k
at a time, and return the modified list.
k is a positive integer and is less than or equal to the length of the
linked list.
Use only O(1) extra memory space.
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
A naive approach would be to use another stack to reverse the nodes of the linked list and then create a new linked list with reversed nodes. The time complexity is O(n) as we traverse the complete linked list. The space complexity is O(n) for storing the nodes in a reversed linked list and O(k) for storing the k number of elements in a stack.
The optimized approach is to use less space in memory. The solution can be divided into the following parts:
- Count and check if there are k nodes present in the linked list
- Reverse sublist of length k
- Connect the reversed sublist with the rest of the linked list
- Repeat the process until there are less than k nodes left in the linked list
#92 Given the head
of a singly linked list and two integers left
and right
where left <= right
, reverse the nodes of the list from position left
to position right
, and return the reversed list.