92. Reverse Linked List II

Solution 1: Recursive Swap NodeValue

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        globLftNode = head
        gRecursiveStop = False
        def recurseRev(tailNode, lftIdx, rhtIdx):
            nonlocal globLftNode, gRecursiveStop

            if rhtIdx == 1:
                return
            if lftIdx > 1:
                globLftNode = globLftNode.next
            tailNode = tailNode.next
            
            recurseRev(tailNode, lftIdx - 1, rhtIdx - 1)

            if globLftNode == tailNode or tailNode.next == globLftNode:
                gRecursiveStop = True
            if not gRecursiveStop:
                globLftNode.val, tailNode.val = tailNode.val, globLftNode.val
                globLftNode = globLftNode.next

        recurseRev(head, left, right)
        return head

Time Complexity: O(N)
Space Complexity: O(N) // Recursive call stack

Solution 2: Iterative + Stack

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dmyNode = ListNode(next = head)
        currNode = dmyNode
        stack = []
        listIdx = 0

        # Move until prevNode of left interval starting node
        while listIdx < left - 1:
            currNode = currNode.next
            listIdx += 1
        prevNode = currNode

        # Keep push node to stack (Use the LIFO property to simulate recursive call stack)
        while listIdx < right:
            currNode = currNode.next
            stack.append(currNode)
            listIdx += 1
        origRestNode = currNode.next

        # Change link of node
        while len(stack):
            prevNode.next = stack.pop()
            prevNode = prevNode.next
        prevNode.next = origRestNode
        return dmyNode.next

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Iterative Swap Node

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dmyNode = ListNode(next = head)
        prev = dmyNode
        for _ in range(left - 1):
            prev = prev.next

        # e.g, dmy -> 1 -> 2 -> 3 -> 4 -> 5 (left=2 right=4)
        #            pre  strt then
        strt = prev.next
        then = strt.next
        for _ in range(right - left):
            strt.next = then.next
            then.next = prev.next
            prev.next = then
            then = strt.next
        return dmyNode.next

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/reverse-linked-list-ii/solutions/215957/reverse-linked-list-ii/
https://blog.csdn.net/weixin_44737922/article/details/125905679
https://leetcode.com/problems/reverse-linked-list-ii/solutions/30666/simple-java-solution-with-clear-explanation/?orderBy=most_votes
https://leetcode.com/problems/reverse-linked-list-ii/solutions/30709/talk-is-cheap-show-me-the-code-and-drawing/?orderBy=most_votes

Follow-up: 716. Max Stack