Q23 PepCoding | Segregate Node Of Linkedlist Over Pivot Index

import java.util.*;

class Main {
  public static Scanner scn = new Scanner(System.in);

  public static class ListNode {
    int val = 0;
    ListNode next = null;

    ListNode(int val) {
      this.val = val;
    }
  }

  public static ListNode segregate(ListNode head, int pivotIdx) {
    if(head == null || head.next == null) return head;
    
    ListNode curr = head;
    ListNode prev = null;
    int val = 0;
    ListNode pivot = null;
    
//traverse till pivot and isolate it from the LL    
        
        while(pivotIdx-- >0){
            prev = curr;
            curr = curr.next;
        }
            val = curr.val;
            pivot = curr;
            
//element smaller than pivot element can exist after pivot which will fuck the order of the LL therefore we will add back the pivot element in the end       


//if pivot is 1st element then prev will remain null which will give null point exception
        if(prev == null){       
            head = head.next;
        }    

//if pivot is any other element        
        else{
            prev.next = curr.next; 
            curr.next = null;
        }
    
            curr = head;

//making two seperate LL 

        ListNode greater = new ListNode(-1);
        ListNode ghelp = greater;
        
        ListNode smaller = new ListNode(-1);
        ListNode shelp = smaller;
        
        
        while(curr!= null){
            
            if(curr.val <= val){
                shelp.next = curr;
                shelp = curr;
            }
            else{
                ghelp.next = curr;
                ghelp = curr;
            }
            curr = curr.next;
        }
        
//adding pivot index to end of smaller
        shelp.next = pivot;
        shelp = shelp.next;
        
//now combining normally
        shelp.next = greater.next;
        ghelp.next = null;
        
        return smaller.next;
  }

  public static void printList(ListNode node) {
    while (node != null) {
      System.out.print(node.val + " ");
      node = node.next;
    }
  }

  public static ListNode createList(int n) {
    ListNode dummy = new ListNode(-1);
    ListNode prev = dummy;
    while (n-- > 0) {
      prev.next = new ListNode(scn.nextInt());
      prev = prev.next;
    }

    return dummy.next;
  }

  public static void main(String[] args) {
    int n = scn.nextInt();
    ListNode h1 = createList(n);
    int idx = scn.nextInt();
    h1 = segregate(h1, idx);
    printList(h1);
  }
}