Reverse Linked List II

Reverse Linked List II 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.

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), where n is the number of nodes in the list. We traverse the list once to reach the left position, and perform up to (right-left) pointer changes, and finally traverse the list to convert it to a vector. time and O(n), due to the space needed to store the output vector<int> and the temporary linked list built from the input vector. 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
• All coding practice problems

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