Java O(n) time solution with O(1) space


  • 0
    V
    public class Solution {
        
        public int getListLength(ListNode node)
        {
            int len = 0;
            
            while(node != null)
            {
                node = node.next;
                ++len;
            }
            
            return len;
        }
        
        public ListNode reverseKGroup(ListNode head, int k) {
            
            ListNode prev = null,
                     curr = head,
                     temp = null,
                     last_group_tail = null,
                     group_first_node = null;
             
            int len = getListLength(head);
            
            if(len < k)
                return head;
                
            int no_of_groups = len / k;
            
            while(no_of_groups-- > 0)
            {
                group_first_node = curr;
                
                    for(int i=1;i<=k;++i)
                    {
                        temp = curr.next;
                        curr.next = prev;
                        prev = curr;
                        curr = temp;
                    }
                    
                  if(last_group_tail == null)
                    {
                        last_group_tail = group_first_node;
                        head = prev;
                    }
                    else
                    {
                        last_group_tail.next = prev;
                        last_group_tail = group_first_node;
                    }
                    
                prev = null;
            }
            
            if(len % k != 0)
            {
                last_group_tail.next = curr;
            }
            
            
            return head;
        }
    }
    

Log in to reply
 

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