educative.io

Educative

Incorrect solution for Reverse every K-element Sub-list

The solution given by the author seems to give us the wrong solution. The reason is when a sublist has less then k nodes it still reverses it.
Eg: Given n = 1,2,3,4,5,6,7,8 & k = 3
first we would reverse the first k nodes
n = 3-2-1-4-5-6-7-8
Then we would reverse the nest k nodes
n = 3-2-1-6-5-4-7-8
This should the actual solution, but the answer given by the admin seems to reverse the next 2 nodes as well.
n = 3-2-1-6-5-4-8-7

Instead we should first iterate over the list k nodes and see if there are enough nodes to reverse and then we reverse the first set of nodes. Repeat the process till there are k possible nodes to reverse, if not then add rest of the remaining nodes without reversing them.

Here’s the right code :slight_smile:
class ReverseEveryKElements {

  public static ListNode reverse(ListNode head, int k) {
    if (k < 2 || head == null) {
      return head;
    }

    ListNode curr = head;
    ListNode itrHead = head;
    ListNode prev = null;

    while (itrHead != null) {
      int count = 0;
      for (int i = 0; i < k && itrHead != null; i++) {
        itrHead = itrHead.next;
        count++;
      }

      if (count == k) {
        ListNode rev_head = reverseSublist(curr, k);
        if (prev == null) {
          head = rev_head;
        } else {
          prev.next = rev_head;
        }

        prev = curr;
        curr = itrHead;
      } else {
        if (prev != null) {
          prev.next = curr;
        }
      }
    }
    return head;
  }

  public static ListNode reverseSublist(ListNode node, int k) {
    ListNode curr = node;
    ListNode prev = null;
    ListNode next = null;

    for (int i = 0; i < k && curr != null; i++) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    return prev;
  }

I suppose the course’s staff has already fixed the problem’s statement:

If, in the end, you are left with a sub-list with less than ‘k’ elements, reverse it too.

Actually, the ask to not reverse last set of nodes less than k, is a Hard question in leetcode (#25).

We can just put a check to have minimum k nodes to achieve same. Posting the code in case anyone needs it.

public ListNode reverseKGroup(ListNode head, int k) {
        
        if(head==null || head.next==null)
            return head;
        
        if(k<=1)
            return head;
        
        ListNode previousNode = null;
        ListNode currentNode = head;
        ListNode nextNode = null;
        
        ListNode lastNodeOfFirstPart = null;
        ListNode startNodeOfSecondPart = null;
        
        //result must be reurned as first kth Node, for 1->2>3->4  it will be 2 if K==2 OR it will be 3 if k==3;
        
        while(true){
            
            lastNodeOfFirstPart = previousNode;
            startNodeOfSecondPart = currentNode;//it will be 1,3,5, for k==2           
           
            //check the number of nodes available to start with, if less than k break
            int nodecounter=0;
            ListNode tempCurrent = currentNode;
            while(tempCurrent!=null && nodecounter <=k){
                nodecounter++;
                tempCurrent = tempCurrent.next;
            }
            
            if(nodecounter<k)
                break;   //breaking if less than k nodes.
  

            for(int i=1; currentNode!=null && i<=k;i++){      
                nextNode = currentNode.next;
                currentNode.next = previousNode;
                previousNode = currentNode;
                currentNode = nextNode;
            }    
            
            if(lastNodeOfFirstPart!=null)
                lastNodeOfFirstPart.next = previousNode;
            else
                head = previousNode;//for first iteration this will be the last node of firt K group.
            
            startNodeOfSecondPart.next = currentNode; //this is tricky??
            //above is needed to have link  between firs reversed pard and 2nd start part ->1->3
                        
            previousNode = startNodeOfSecondPart;//This is the 1->2  1 here.
            
            if(currentNode==null){
                //System.out.println("currentNode is NULL-->");
                break; 
            }           
        }
        return head;
    }
1 Like