using System;

public class Program

{

    public static void Main()

    {

        LinkedList list = new LinkedList();

        //3 -> 5 -> 10 -> 2 -> 8 -> 2 -> 1

        list.head = new Node(3);

        list.head.next = new Node(5);

        list.head.next.next = new Node(10);

        list.head.next.next.next = new Node(2);

        list.head.next.next.next.next = new Node(8);

        list.head.next.next.next.next.next = new Node(2);

        list.head.next.next.next.next.next.next = new Node(1);

        Console.WriteLine("Linked list before reversing:");

        list.printAllNodes(list.head);

        list.Partition(list.head,5);

        Console.WriteLine();        

        Console.WriteLine("Linked list after Partition:");

        list.printAllNodes(list.head);      

    }

}

public class Node

{

    public Node next;

    public int data;

    public Node(int data)

    {

        this.data=data;

    }

}

public class LinkedList

{

    public Node head;

    public void printAllNodes(Node head)

    {

        Node current=head;

        while(current!=null)

        {

            Console.Write("{0} ",current.data);

            current=current.next;

        }

    }

    public void Partition(Node head,int x)

    {

        Node dummy1=new Node(0), dummy2=new Node(0);

        Node curr1=dummy1, curr2=dummy2;

        while(head!=null)

        {

            if(head.data<x)

            {

                curr1.next=head;

                curr1=head;

            }

            else

            {

                curr2.next=head;

                curr2=head;

            }

            head=head.next;

        }

        curr2.next=null;

        curr1.next=dummy2.next;

    }

}