Recursive solution using 2 passes in Java


  • 0
    N
    public class Solution {
    ListNode first = null;
    
    //this method reverses a LinkedList for counter no. of nodes
    private ListNode reverse(ListNode node, int counter){
        counter--;
        
        if(counter == 0){
            first = node;
            return node;
        }
        
        ListNode ret = reverse(node.next, counter);
        node.next = ret.next;
        ret.next = node;
        return node;
    }
    
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        int len = 0;
        ListNode temp = head;
        
        //find the length of the LinkedList
        while(temp != null){
            len++;
            temp = temp.next;
        }
        
        //if the LinkedList is smaller than k, just return the head;
        if(len < k) return head;
        
        //point temp back to head
        temp = head;
        
        //number of possible groups in the LinkedList
        int numOfGroups = len/k;
        ListNode prev = null;
        
        temp = reverse(temp, k);
        prev = temp; //preserve the last node as previous
        head = first; //preserve the first node as its the head
        temp = temp.next; 
        numOfGroups--;
        
        while(temp != null && numOfGroups != 0){
            temp = reverse(temp, k);
            prev.next = first;
            prev = temp;
            
            //decrement the number of passes
            numOfGroups--;
            
            //move to the next node
            temp = temp.next;
        }
        
        return head;
        
    }
    

    }


  • 1
    R

    Your code is too long.
    Simpler version for recursion: (With only one pass except for the last group)
    just to show you, it is a simpler version of your code, but not using constant memory

    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null){
                return null;
            }
            int count = 1;
            ListNode previous = head;
            ListNode current = head.next;
            ListNode next = null;
            while (count < k && current != null){
                next = current.next;
                current.next = previous;
                previous = current;
                current = next;
                count++;
            }
            //if less than k, reverse it back (only happened in the very end)
            if (count != k){
                head.next = null;
                return reverseKGroup(previous, count);
            }
            head.next = reverseKGroup(current, k);
            return previous;
        }
    }

Log in to reply
 

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