Share a Python solution, one pass, O(n)


  • 0
    C

    Let me know how do you think:

    def reverseBetween(self, head, m, n):
        if m == n:
            return head
            
        pre_start = sentinel = ListNode(0)
        sentinel.next = head
        
        # find pre start node
        for _ in range(m - 1):
            pre_start = pre_start.next
        
        # reverse    
        start = prev = pre_start.next
        for _ in range(n - m + 1):
            next_node = start.next
            start.next = prev
            prev = start
            start = next_node
        
        # connect the reversed
        pre_start.next.next = next_node
        pre_start.next = prev
        
        return sentinel.next

Log in to reply
 

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