Iterative Solution for Reverse Nodes in Groups of K Nodes


  • 0

    The iterative solution is better as the recursive solution may use Stack memory and if you have a very large quantity of data like millions of node in LinkedList, your code may not provide the desired solution, give an error instead.

    public ListNode reverseKGroup(ListNode head, int k) {
            if(head==null || head.next==null || k==1){
                return head;
            }
            int l = 0;
            //To find length of LL
            ListNode temp = head;
            while(temp!=null){
                temp = temp.next;
                l++;
            }
            if(k>l){
                return head;
            }
            boolean flag = true;
            ListNode c = head;
            ListNode p = null;
            ListNode n = null;
            ListNode tail1 = null;
            ListNode tail2 = null;
            while(c!=null){
                int i=0;
                if(flag){
                    tail1 = c;
                }
                else{
                    tail2 = tail1;
                    tail1 = c;
                }
                //remaining nodes are less than k
                if(k>l){
                    if(tail2!=null){
                        tail2.next = tail1;
                    }
                    break;
                }
                p=null;
                //reversing k nodes
                while(i<k && c!=null){
                    //System.out.println("p");
                    n = c.next;
                    c.next = p;
                    p=c;
                    c = n;
                    i++;
                }
                l-=k;
                if(flag){
                    flag=false;
                    head = p;
                }
                else{
                    tail2.next = p;
                }    
            }
            return head;
        }
    

  • 0
    S
    
    
    
    ``` private static ListNode ReverseKList(ListNode head, int k)
            {
               
                var setGroup = true;
                ListNode firstNode = null;
                ListNode secondTail = null;
                ListNode firstTail = null;
                ListNode prev = null;
    
                if (head == null || head.Next == null || k == 1)
                {
                    return head;
                }
    
                int length = 0;
                
                //find length of list
                ListNode temp = head;
                while (temp != null)
                {
                    temp = temp.Next;
                    length++;
                }
                if (k > length)
                {
                    return head;
                }
    
                //reverse the list in k group
                var group = k;
                while (head != null)
                {
    
                    //reverse the list
                    var next = head.Next;
                    head.Next = prev;
                    prev = head;
                    head = next;
    
    
                    if (setGroup)
                    {
                        // get the first group tail node address 
                        // pre will have tail node intilally for each iteration of a group
                        if (firstTail == null)
                            firstTail = prev;
    
                        secondTail = prev;
                        setGroup = false;
                    }
    
    
                    if (--group == 0 || head == null)
                    {
                        if(firstNode==null)
                        firstNode = prev;
    
                        else
                        {
                            //link the two reversed grouped
                            firstTail.Next = prev;
                            firstTail = secondTail;
                            
                        }
                        prev = null;
                        group=k;
                        setGroup = true;
                    }
    
    
                }
                return firstNode;
            }

Log in to reply
 

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