/*
Given a linked list and an integer X, partition the LL around X, such that all nodes less than X come before all nodes greater than X. If X is contained within the list, then those nodes need

to be after the elements less than X and before the elements greater than X, i.e. they should appear between the left and right partitions.


You can also see if you can preserve the order for elements on either side of the partition. For instance, for given LL 2, 6, 5, 7, 1 and X = 5, the answer should be 2, 1, 5, 6, 7 only, instead of 1, 2, 5, 6, 7.

Input format
N - An integer denoting the number of nodes in the linked list.

N integers follow where ith integer denotes the ith node value in the linked list

X - An integer denoting the value that you must use to partition the given list

Output format
Return the head after partitioning the list

Constraints
1 <= N <= 10^5

-10^9 <= value, X <= 10^9

Sample Input 1
7

3 5 8 5 10 2 1

5

Sample Output 1
3 2 1 5 5 8 10

Explanation 1
The nodes [3], [1] and [2] are less than [5] so they are present before [8] and [10].

There are also other possible answers for the same input.

Sample Input 2
5

3 1 3 1 4

2

Sample Output 2
1 1 4 3 3

Explanation 2
All nodes with values less than 2 come before all nodes with values greater than 2.
*/

/*
class ListNode{
    constructor(val){
        this.val = val;
        this.next = null;
    }
*/
/*
In JavaScript, when you pass an object (like a ListNode or any other object) as an argument to a function, you are actually passing a reference to that object. However, there is a distinction between passing by value and passing by reference that is important to understand.

In the case of your insertNode function, you are passing newHead and newLastPointer as arguments. These arguments hold references to objects (ListNode instances) that exist outside of the function. When you modify the properties of the object that newHead and newLastPointer reference, those changes are reflected outside of the function.

However, when you reassign newHead and newLastPointer to new values inside the insertNode function, you are not modifying the original references that were passed as arguments. Instead, you are creating new local references within the function that point to different objects. These new references do not affect the original references outside of the function.

To update newHead and newLastPointer effectively, you can return the new values from the insertNode function and assign them outside of the function. Here's how you can modify the insertNode function:
*/
function insertNode(newHead,newLastPointer,newVal){
      if(newHead==null){
            newHead=new ListNode(newVal);
            newLastPointer=newHead;
      }
      else{
            newLastPointer.next=new ListNode(newVal);
            newLastPointer=newLastPointer.next;
      }
      return [newHead,newLastPointer];
}
/**
 * @param {ListNode} head
 * @param {number} X
 * @return {ListNode}
 */
function partition(head, x) {
     let newHead=null;
     let currNode=head;
     let newLastPointer=null;
     // two iterations needed
     while(currNode!=null){
           if(currNode.val<x){
                 [newHead, newLastPointer]=insertNode(newHead,newLastPointer,currNode.val);
           }
      //      console.log(newHead)
           currNode=currNode.next;
     }
     // insertNode(newHead,newLastPointer,x);
     currNode=head;
     while(currNode!=null){
           if(currNode.val==x){
                [newHead, newLastPointer]= insertNode(newHead,newLastPointer,currNode.val)
           }
           currNode=currNode.next
     }

     currNode=head;
     while(currNode!=null){
           if(currNode.val>x){
                 [newHead, newLastPointer]=insertNode(newHead,newLastPointer,currNode.val)
           }
           currNode=currNode.next
     }
//      console.log(newHead)
     return newHead;


}