Solution with O(n) time complexity and O(1) space complexity-No recursion


  • 1
    L
    class Solution:
        # @param head, a ListNode
        # @param k, an integer
        # @return a ListNode
        def reverseKGroup(self, head, k):
            if head==None or head.next==None or k<=1:
                return head
            previous=ListNode(0)
            previous.next=head
            cur=head
            count=0
            while cur!=None:   #count: how many elements in list
                count+=1
                cur=cur.next
            if count<k:        #check first
                return head
            numK=count/k       #numK: times of reverse
            i=0
            pre=previous
            cur=head
            while i<numK:      #loop numK times
                j=1
                while j<k:       #each loop: reverse k nodes(like insertion)
                    temp=cur.next
                    cur.next=temp.next
                    temp.next=pre.next
                    pre.next=temp
                    j+=1
                pre=cur
                cur=cur.next
                i+=1
            return previous.next`enter code here`
    

    The main idea: count the number of elements in the linked list first; compare count with k, if less than k, return head; then compute numK ,times of k reverse. Then loop numK times and in each loop, reverse k nodes. The total complexity is O(n) time complexity and O(1) space complexity


  • 0
    X

    Brillant solution!

    I wrote a Python version for reference.

    class Solution:
        # @param head, a ListNode
        # @param k, an integer
        # @return a ListNode
        def reverseKGroup(self, head, k):
            length = 0
            ptr = head
            while ptr is not None:
                length += 1
                ptr = ptr.next
            dummy_head = ListNode(0)
            dummy_head.next = head
            prev = dummy_head
            end = prev.next
            first = end
            for i in range(length//k):
                for j in range(k-1):
                    insert = end.next
                    prev.next = insert
                    end.next = insert.next
                    insert.next = first
                    first = insert
                prev = end
                end = prev.next
                first = end
            return dummy_head.next
    

Log in to reply
 

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