Succinct iterative Python, O(n) time O(1) space


  • 20
    Z

    Use a dummy head, and

    l, r : define reversing range

    pre, cur : used in reversing, standard reverse linked linked list method

    jump : used to connect last node in previous k-group to first node in following k-group

    def reverseKGroup(self, head, k):
        dummy = jump = ListNode(0)
        dummy.next = l = r = head
        
        while True:
            count = 0
            while r and count < k:   # use r to locate the range
                r = r.next
                count += 1
            if count == k:  # if size k satisfied, reverse the inner linked list
                pre, cur = r, l
                for _ in range(k):
                    cur.next, cur, pre = pre, cur.next, cur  # standard reversing
                jump.next, jump, l = pre, l, r  # connect two k-groups
            else:
                return dummy.next

  • 0
    H

    Nice Pythonic way to perform the 3 variable reassignment in one line.


  • 0
    R

    Can you explain how the 3 variable tuple unpacking works ? If I unwind it , I usually get
    AttributeError: 'NoneType' object has no attribute 'next'


  • 0
    H

    @rahul8590 Python multiple value assignments work by first evaluating the right hand side.

    All variables on the right-hand side are first evaluated and then assigned to the left hand-side variables going from left->right.


  • 0
    M

    @rahul8590 Also, all previous values are considered. (values of all variables before the statement)


Log in to reply
 

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