Python 7 lines, beat 90% with explanation


  • 0

    The idea is:

    1. find the 'start' of the linked list needed to be reversed
    2. make (n - m) 'moves' to reverse

    Here is the 'move':
    We move the next one to the beginning to the reversed linked list, for example:
    A move will change the linked list from:
    a -> (d -> c-> b) -> e -> f
    to:
    a -> (e -> d -> c-> b) -> f
    where a is 'beforeStart' and '()' contains reversed linked list.

    class Solution(object):
        def reverseBetween(self, head, m, n):
            hat = ListNode(0)
            hat.next, start = head, hat
    
            for i in range(m):
                beforeStart, start = start, start.next
    
            for i in range(n - m):
                beforeStart.next, start.next, beforeStart.next.next = start.next, start.next.next, beforeStart.next
    
            return hat.next
    
    

Log in to reply
 

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