Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

        public void Partition(int x)

        {

            if (this.Head == null)

            {

                return;

            }

            LinkedListNode headSmall = new LinkedListNode(-1, this.Head);

            LinkedListNode currSmall = headSmall, currLarge = null, headLarge = null, curr = this.Head;

            while(curr != null)

            {

                if (curr.Value < x)

                {

                    currSmall.Next = curr;

                    currSmall = curr;

                    curr = curr.Next;

                    currSmall.Next = null;

                }

                else

                {

                    if (headLarge == null)

                    {

                        headLarge = curr;

                        currLarge = headLarge;

                        curr = curr.Next;

                        currLarge.Next = null;

                    }

                    else

                    {

                        currLarge.Next = curr;

                        currLarge = curr;

                        curr = curr.Next;

                        currLarge.Next = null;

                    }

                }

            }

            currSmall.Next = headLarge;

            this.Head = headSmall.Next;

        }