Python Stack Solution


  • 0

    Basically find the area we need to reverse, push it onto a stack to get the reverse order, then pop them all back.

    class Solution(object):
        def reverseBetween(self, head, m, n):
            stack = []
            dummy = ListNode(0)
            dummy.next = head
            before = runner = dummy
            # advance runner until we hit one node before the reversal process
            for i in range(m-1):
                runner = runner.next
            before = runner
            # the next node is where we want to start reverse. We reverse the next n-m+1 nodes
            for i in range(n-m+1):
                runner = runner.next
                stack.append(runner)
            # keep track of the node we want to append next
            after = runner.next
            while stack:
                before.next = stack.pop()
                before = before.next
            before.next = after
            return dummy.next
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.