Description
https://leetcode.com/problems/reverse-linked-list-ii/
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 <= 5001 <= left <= right <= n
Follow up: Could you do it in one pass?
Explanation
First, find out the node values need to be reversed and the positions where the reverse begins. Then build a reversed node list. Thirdly, combine the reversed node list with the original node list.
Python Solution
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
i = 1
in_range_node_values = []
dummy = ListNode(0)
dummy.next = head
prev_left = dummy
after_right = None
while head:
if i == left - 1:
prev_left = head
elif i == right + 1:
after_right = head
elif i >= left and i <= right:
in_range_node_values.append(head.val)
prev = head
head = head.next
i += 1
in_range_node_values = in_range_node_values[::-1]
reversed_in_range_node_list = self.get_node_list(in_range_node_values)
prev_left.next = reversed_in_range_node_list
head = dummy.next
while head.next:
head = head.next
head.next = after_right
return dummy.next
def get_node_list(self, values):
dummy = ListNode(0)
prev = dummy
for value in values:
node = ListNode(value)
prev.next = node
prev = node
return dummy.next
- Time Complexity: O(N).
- Space Complexity: O(N).