Leetcode 92. 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 <= 500
• 1 <= left <= right <= n

Follow up: Could you do it in one pass?

My solution is finding the reversed head and tail node and keep the node index in hash map, then iterate through and relink the nodes.

# 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: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == right:
            return head

        node_map = {}

        curr = head
        index = 1

        while index <= right:
            node_map[index] = curr
            curr = curr.next
            index += 1

        if left != 1:
            reverse_head = node_map[left - 1]
        else:
            reverse_head = node_map.get(index - 1)
            right -= 1
            head = reverse_head

        for i in range(right, left-1, -1):
            reverse_head.next = node_map[i]
            reverse_head = reverse_head.next
        
        reverse_head.next = curr

        return head