92. Reverse Linked List II

Medium

---

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?

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == right or not head:
            return head
        starting = head
        stack = []
        count = 0
        leftNodePrev = None
        rightNodeNext = None
        prev = None
        while head:
            count += 1
            if left <= count <= right:
                if left == count:
                    leftNodePrev = prev
                if right == count:
                    rightNodeNext = head.next
                stack.append(head)
            prev = head
            head = head.next
        d = dummy = ListNode()
        while stack:
            dummy.next = stack.pop()
            dummy = dummy.next
        if leftNodePrev:
            leftNodePrev.next = d.next
        else:
            starting = d.next
        dummy.next = rightNodeNext
        return starting