Leetcode 92. Reverse Linked List II
head of a singly linked list and two integers
left <= right, reverse the nodes of the list from position
left to position
right, and return the reversed list.
Input: head = [1,2,3,4,5], left = 2, right = 4
Input: head = , left = 1, right = 1
- The number of nodes in the list is
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
Basically we need to reverse the linked list. But we don’t want to reverse the linked list fully. There is a left and right limit given and we only need to reverse those area. So we need to properly get this part and apply our normal reversing of linked list algorithm.
So we need to make use of some pointers say previous, current and update current and previous until left limit > 1. Now just store the current previous and current node. Then continue our reversal until right > 0, and make sure to adjust the node properly as there can be some null edge cases which should be handled properly.
- Let previous = null and current = head.
- Until left > 1, do left- - , right- - also move previous = current and current = current.next. This is the point where we start our reversal, ie when left becomes 1.
- Now store the previous node and current node.
- Until right > 0, do the reversal process and do right- -.
- Handle the null cases which may occur in some cases.
We are traversing through the linked list once and say the size of the linked list is n. So our time complexity will be O(n).
We are not making use of any extra space, so our space complexity will be O(1).