Iterative solution using helper function reverse list and sub dividing the list into k smaller lists


  • 0
    S

    Easy solution using a helper function reverse list, divide the list into smaller lists of size k, call the reverse list function on the sublist, rearrange the pointers and you would reach the solution. A dummy pointer is used to make the implementation easy.
    '''
    class Solution {

    public ListNode reverseKGroup(ListNode head, int k) {
         ListNode tmp = head;
         ListNode dummy = new ListNode(0);
         ListNode start = dummy;
    
         dummy.next = head
    
        while( tmp!= null){
         int c = 1;
        while(c<k && tmp!= null){
            tmp = tmp.next;
            c++;
        }
        if(tmp!=null){    
        ListNode newList = tmp.next;
        tmp.next = null;
        ListNode reversed = reverseList(dummy.next);
        ListNode initial = dummy.next;
        dummy.next = reversed;
        dummy = initial;
        dummy.next = newList;    
        tmp = newList;    
         }
       }
        return start.next;
    }
    public ListNode reverseList(ListNode head){
        if(head == null)
            return head;
        ListNode prev = null;
        ListNode tmp = head;
        ListNode nextP = head.next;
        while(tmp != null){
            tmp.next = prev;
            prev = tmp;
            tmp = nextP;
            if(tmp != null)
            nextP = tmp.next;
        }
        return prev;
    }
    

    }
    '''


Log in to reply
 

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