Partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

package linkedlist.singly;

 
// Write code to partition a linked list around a value x, such that all nodes less than x
// come before all nodes greater than or equal to x.
public class PartitionLinkList {

 ListNode startNode;

 public static void main(String[] args) {
  new PartitionLinkList();
 }
 public PartitionLinkList() {
  ListNode n1 = new ListNode(7);
  ListNode n2 = new ListNode(6);
  ListNode n3 = new ListNode(5);
  ListNode n4 = new ListNode(4);
  ListNode n5 = new ListNode(3);
  ListNode n6 = new ListNode(2);
  ListNode n7 = new ListNode(1);

  startNode = n1;

  n1.setNext(n2);
  n2.setNext(n3);
  n3.setNext(n4);
  n4.setNext(n5);
  n5.setNext(n6);
  n6.setNext(n7);

  ListNode l1 = partitionWay(startNode, 7);
  printLinkList(l1);
 } 
 
 //Solution : Idea is to create 2 list one with data having value smaller then i and one with data having value greater then i.
 //Now, just scan the complete list, in each iteration check the value of current node is less then i,
 //If yes, put it in smallerNodeListEnd.
 //If no, put it in largerNodeListEnd.
 //Now, the question is if we are adding data at smallerNodeListEnd and largerNodeListEnd, what about the start pointer of 2 list, are we losing it.
 //we took 2 additional pointers for start preserving of 2 list.
 private ListNode partitionWay(ListNode startNode, int i) {
  ListNode smallerNodeListStart = new ListNode(-1); //Dummy data just to avoid condition in loop as if start initially is null the do initialization.
  ListNode largerNodeListStart = new ListNode(-1); //Dummy data just to avoid condition in loop as if start initially is null the do initialization.

  ListNode smallerNodeListEnd = smallerNodeListStart;
  ListNode largerNodeListEnd = largerNodeListStart;
  ListNode temp = startNode;

  while(temp!=null){
   if(temp.getData()<i){
    smallerNodeListEnd.setNext(temp); 
    smallerNodeListEnd=temp;
   }else{
    largerNodeListEnd.setNext(temp); 
    largerNodeListEnd=temp;
   }
   temp = temp.getNext();
  }
  largerNodeListEnd.setNext(null); //Larger node may have extra data at end, remove that.

  smallerNodeListEnd.setNext(largerNodeListStart.getNext());
  return smallerNodeListStart.getNext();
 }

 //Solution1 : conditional based approach for initializing start pointer of 2 list, rest the solution is same as solution 1 above.
 public ListNode partitionWay1(ListNode n, int x) {
  ListNode beforeStart = null;
  ListNode beforeEnd = null;
  ListNode afterStart = null;
  ListNode afterEnd = null;

  while (n != null) {
   ListNode next = n.getNext();
   n.setNext(null);

   if (n.getData() < x) {
    if (beforeStart == null) {
     beforeStart = n;
     beforeEnd = beforeStart;
    } else {
     beforeEnd.setNext(n);
     beforeEnd = beforeEnd.getNext();
    }
   } else {
    if (afterStart == null) {
     afterStart = n;
     afterEnd = afterStart;
    } else {
     afterEnd.setNext(n);
     afterEnd = afterEnd.getNext();
    }
   }
   n = next;
  }

  if (beforeStart == null) {
   return afterStart;
  }

  beforeEnd.setNext(afterStart);
  return beforeStart;
 }

 private void printLinkList(ListNode startNode) {
  ListNode tempNode = startNode;
  while(tempNode!=null){
   System.out.print(tempNode.getData() + " ");
   tempNode = tempNode.getNext();
  }
 }
}

class ListNode{
 public ListNode next;
 public int data;

 // Creates an empty node.
 public ListNode(){
  next = null;
  data = Integer.MIN_VALUE;
 }

 // Creates a node storing the specified data.
 public ListNode (int data){
  next = null;
  this.data = data;
 }

 // Returns the node that follows this one.
 public ListNode getNext(){
  return next;
 }

 // Sets the node that follows this one.
 public void setNext (ListNode node){
  next = node;
 }

 // Returns the data stored in this node.
 public int getData(){
  return data;
 }

 // Sets the data stored in this node.
 public void setdata (int elem){
  data = elem;
 }

 // Sets the data stored in this node.
 public String toString (){
  return Integer.toString(data);
 } 
}