Intuitive but recursive. O(N) time O(N/k) stack space.


  • 0
    S
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if(head==null || head.next ==null || k <=1) return head;
            
            int count = 0;
            ListNode current = head;
            ListNode prev = null;
            while(current !=null && count <k){
                prev = current;
                current = current.next;
                count++;
            }
            
            if(count !=k){
                return head; //reverse not needed
            } else{
                prev.next = null; //break connection otherwise, infinite loop
                ListNode tempHead = reverseKGroup(current, k);
                ListNode newHead = reverse(head);
                head.next = tempHead;
                return newHead;
            }        
        }
        
        private ListNode reverse(ListNode head){
            ListNode dummy = new ListNode(0);
            
            while(head !=null){
                ListNode temp = head.next;
                head.next = dummy.next;
                dummy.next = head;
                head = temp;
            }
            
            return dummy.next;
        }
    }
    

Log in to reply
 

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