Python one pass iterative solution


  • 23
    G

    The idea is simple and intuitive: find linkedlist [m, n], reverse it, then connect m with n+1, connect n with m-1

    class Solution:
        # @param head, a ListNode
        # @param m, an integer
        # @param n, an integer
        # @return a ListNode
        def reverseBetween(self, head, m, n):
            if m == n:
                return head
    
            dummyNode = ListNode(0)
            dummyNode.next = head
            pre = dummyNode
    
            for i in range(m - 1):
                pre = pre.next
            
            # reverse the [m, n] nodes
            reverse = None
            cur = pre.next
            for i in range(n - m + 1):
                next = cur.next
                cur.next = reverse
                reverse = cur
                cur = next
    
            pre.next.next = cur
            pre.next = reverse
    
            return dummyNode.next

  • 0
    S
    This post is deleted!

  • 0
    I

    what is pre.next.next?


  • 0
    S

    @IWantToPass pre.next refers to the end of the reversed list (first prev = None), pre.next.next links it to the latter part of the none reversed list.(1-->2, 2-->5)


  • 1
    R

    Great solution. I have the same idea but was struggling on how to implement it.
    However I am confused why in the end return dummyNode.next instead of head.
    shouldn't dummyNode.next==head? but when I tried the latter, the code is not accepted.
    Would you elaborate this part a little bit?@Google
    Thanks!!!


Log in to reply
 

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