iterative & recursive solutions


  • 0
    G
    • O(n) time & O(1) space:
    # Definition for singly-linked list.
    class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None
    
    class Solution(object):
        def reverseKGroup(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            def reverse(head, end):
                start, s2 = head.next, head.next
                b2 = end.next
                end.next = None
                pre, cur = start, start.next
                while cur is not None:
                    pre.next = cur.next
                    cur.next = start
                    start = cur
                    cur = pre.next
                head.next = start
                s2.next = b2
                return s2
    
            dummy = ListNode(0)
            dummy.next = head
            i, start, stop = 0, dummy, dummy
            while stop:
                if i == k:
                    i = 0
                    start = stop = reverse(start, stop)
                else:
                    i += 1
                    stop = stop.next
            return dummy.next
    
    • O(n) in time & space:

    Note that this solution is taken from here.

    class Solution(object):
        def reverseKGroup(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            cur, cnt = head, 0
            while cur is not None and cnt < k:
                cur = cur.next
                cnt += 1
            if cnt == k:
                cur = self.reverseKGroup(cur, k)
                while k:
                    tmp = head.next
                    head.next = cur
                    cur = head
                    head = tmp
                    k -= 1
                head = cur
            return head
    
    • iterative version of solution 2, O(n) time & O(1) space:
    class Solution(object):
        def reverseKGroup(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            def rev(start, stop, k):
                while k:
                    tmp = start.next
                    start.next = stop
                    stop = start
                    start = tmp
                    k -= 1
                return stop, start
    
            dummy = ListNode(0)
            dummy.next = head
            preHead = None
            cur, cnt = head, 0
            while cur is not None:
                while cur is not None and cnt < k:
                    cur = cur.next
                    cnt += 1
                if cnt == k:
                    beg, end = rev(head, cur, cnt)
                    if preHead:
                        preHead.next = beg
                    else:
                        dummy.next = beg
                    cnt = 0
                    preHead = head
                    head = cur = end
            return dummy.next
    

Log in to reply
 

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