Simple Python solution, one pass, no additional space, 109ms


  • 8
    C

    The key idea is to keep track of the next_head while reversing the group, tail of the current group is always the start node of the group, once the group reversing is done, next_head is available, simply connect it to tail.

    def reverseKGroup(self, head, k):
        if head is None or k < 2:
            return head
        
        next_head = head
        for i in range(k - 1):
            next_head = next_head.next
            if next_head is None:
                return head
        ret = next_head
        
        current = head
        while next_head:
            tail = current
            prev = None
            for i in range(k):
                if next_head:
                    next_head = next_head.next
                _next = current.next
                current.next = prev
                prev = current
                current = _next
            tail.next = next_head or current
                
        return ret

  • 4
    C

    Also the recursive solution:

    def reverseKGroup(self, head, k):
        if head is None or k < 2:
            return head
        
        ret = head
        for i in range(k - 1):
            ret = ret.next
            if ret is None:
                return head
                
        prev, current = None, head
        for i in range(k):
            _next = current.next
            current.next = prev
            prev = current
            current = _next
            
        head.next = self.reverseKGroup(current, k)
        
        return ret    

  • 0
    R

    Neat solution! Chuntao you are awesome!


  • 0
    C

    @ray8 thank you :)


  • 0
    M

    Really nice solution! Thanks for sharing, and this is my JAVA version:

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k < 2) return head;
        ListNode next_head = head;
        int cnt = 0;
        while (next_head != null && cnt++ < k - 1) {
            next_head = next_head.next;
        }
        if (next_head == null) return head;
        ListNode ret = next_head;
        ListNode curr = head;
        while(next_head != null) {
            cnt = 0;
            ListNode tail = curr;
            ListNode pre = null;
            while (cnt++ < k) {
                if (next_head != null) next_head = next_head.next;
                ListNode next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }
            tail.next = next_head == null ? curr : next_head;
        }
        return ret;
    }

  • 1
    H

    Sorry, but this is certainly not 1-pass.

    According to your code, You first move forward to make sure that you have k-nodes. If you don't you stop the search.
    If you have k nodes, then you begin again and reverse the k-nodes.

    The only way you could even be close to calling this as a single-pass solution is if you used a fast and slow pointer. And reverse in k-groups until the fast pointer hits None.


  • 0
    H

    @humachine agreed. not one pass at all... lol


Log in to reply
 

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