Leetcode 92. Reverse Linked List II

Accepted Code

Problem Statement

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.

Test Cases

Example 1:

Taken from Leetcode.com

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Approach

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.

Algorithm

1. Let previous = null and current = head.
2. 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.
3. Now store the previous node and current node.
4. Until right > 0, do the reversal process and do right- -.
5. Handle the null cases which may occur in some cases.

Time Complexity

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).

Code

Java Code

LeetCodeTopInterviewQuestions/21_Reverse_Linked_List_II.java at master ·…