The linked list is another interesting data structure in Computer Science. They are similar to arrays but instead of storing data in consecutive memory locations in a linked list the data is stored anywhere in the memory and the consecutive elements are connected by storing the next elements memory address to the current element.
The Problem
Given the head of a singly linked list and two integers m and n where m <= n, reverse the nodes of the list from the position m to position n, and return the reversed list.
Example 1:
1
2
Input: head = [1,2,3,4,5], m = 2, n = 4
Output: [1,4,3,2,5]
Example 2:
1
2
Input: head = [5], m = 1, n = 1
Output: [5]
The Solution
To reverse a link in the linked list we have to change the link connecting from currentNode-->nextNode to currentNode<--nextNode for all the node pairs. Here we only need to do this process on the input linked list for the nodes between m and n
Start from the first node of the linked list and move forward until the next node is the mth node.
From mth position to nth position reverse the linked list.
Finally combine the first portion, the middle portion(the reversed portion) and the last portion of the lists.
Let’s write this logic into code as
The time complexity of this solution will be O(n).
References