In-place Reversal of a Linked List

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.