92. Reverse Linked List II
Reverse Linked List II (LeetCode 92) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the In-place Reversal subpattern.
How to solve Reverse Linked List II
Reverse Linked List II is a In-Place Linked List Reversal problem, part of Linked List Manipulation Patterns. Master in-place linked list reversal including full reversal, partial reversal, and k-group reversal techniques.
Work towards the solution in these steps:
- Recall common techniques for manipulating singly linked lists, especially when modifying a segment of nodes in-place.
- Identify the node just before the 'left' position to use as a fixed anchor point for reconnection after reversal.
- Consider reversing the sublist between positions 'left' and 'right' by iteratively re-linking nodes within this range.
The reference solution runs in O(n) time and O(n) space.
The Reverse Linked List II solution and editorial walks through the full approach with reference 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.
Example 1:
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
Follow up: Could you do it in one pass?
Topics and companies
Topics: Linked List.
Reported in interviews at Amazon, Facebook, Microsoft, Oracle, ByteDance.
How to practise Reverse Linked List II on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Reverse Linked List II in the code editor, or read the Reverse Linked List II editorial for a worked solution with its approach and complexity analysis.
Where Reverse Linked List II sits in the DSA pattern sheet
- Linked List Manipulation Patterns pattern guide
- In-place Reversal subpattern
- The full DSA patterns sheet
Problems related to Reverse Linked List II
Other problems that use the same In-place Reversal and Linked List Manipulation Patterns techniques:
- Palindrome Linked List — Easy, same subpattern
- Remove Duplicates from Sorted List — Easy, same subpattern
- Remove Duplicates from Sorted List II — Medium, same subpattern
- Reverse Linked List — Easy, same subpattern
- Reverse Nodes in k-Group — Hard, same subpattern
- Add Two Numbers — Medium, same pattern
Reverse Linked List II FAQ
What is the LeetCode number of Reverse Linked List II?
Reverse Linked List II is LeetCode problem 92, rated Medium.
What pattern is used to solve Reverse Linked List II?
Reverse Linked List II is a In-Place Linked List Reversal problem. It belongs to the Linked List Manipulation Patterns pattern, in the In-place Reversal subpattern.
What is the time complexity of Reverse Linked List II?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Reverse Linked List II?
Reverse Linked List II has been reported in interviews at Amazon, Facebook, Microsoft, Oracle, ByteDance.