using System;

using System.Collections.Generic;

public class Program

{

    // First we need to implement a linked list.

    public class Node

    {   

        public Node(int data)

        {

            this.Data = data;

        }

        public int Data

        {

            get;

            set;

        }

        public Node Next

        {

            get;

            set;

        }

    }

    // Now we need an algorithm of removing duplicates.

    // Easiest way I can think of is to have a Set of integers

    // If it isn't in the set already put it in the set.

    // If it is in the set, remove the next element

    public static Node DuplicateRemoval(Node n)

    {

        if (n == null || n.Next == null)

        {

            return n;   

        }

        Node first = n;

        Node second = n.Next;

        HashSet<int> numSet = new HashSet<int>();

        numSet.Add(n.Data);

        while (second.Next != null)

        {

            if (numSet.Contains(second.Data))

            {

                second = second.Next;

            }

            else

            {

                numSet.Add(second.Data);

                first.Next = second;

                first = second;

                second = second.Next;

            }

        }

        // We need to check the last element in the list.

        // Second should be pointing to the last element in the list.

        if (numSet.Contains(second.Data))

        {

            first.Next = null;

        }

        else

        {

            first.Next = second;

        }

        return n;

    }

    public static Node KthToLast(int k, Node n)

    {

        // Assumption: Kth to last element exists (i.e. 5th to last element in a list of size 3 doesn't exist)

        Node first = n;

        Node second = n;

        // Advance the second pointer k times.

        for (int i = 0; i < k; i++)

        {

            second = second.Next;

        }

        // Advance both pointers until second is null.

        while (second != null)

        {

            first = first.Next;

            second = second.Next;

        }

        // Return first

        return first;

    }

    public static void DeleteMiddleNode(Node n)

    {

        while (n.Next.Next != null)

        {

            n.Data = n.Next.Data;

            n.Next = n.Next.Next;

            n = n.Next;

        }

        n.Data = n.Next.Data;

        n.Next = null;

    }

    public static void PrintLinkedList(Node n)

    {

        if (n == null)

        {

            return;

        }

        while (n.Next != null)

        {

            Console.Write(n.Data + " -> ");

            n = n.Next;

        }

        Console.WriteLine(n.Data);

    }

    public static Node CreateLinkedList(List<int> lst)

    {

        if (lst.Count == 1)

        {

            return new Node(lst[0]);

        }

        Node n = new Node(lst[0]);

        Node first = n;

        for (int i = 1; i < lst.Count; i++)

        {

            n.Next = new Node(lst[i]);

            n = n.Next;

        }

        return first;

    }

    public static void Main()

    {

        //Node linkedList = new Node(4);

        //linkedList.Next = new Node(3);

        //linkedList.Next.Next = new Node(5);

        //PrintLinkedList(linkedList);

        //PrintLinkedList(CreateLinkedList(new List<int>(){ 2, 4, 7 }));

        //PrintLinkedList(CreateLinkedList(new List<int>(){ 2 }));

        //PrintLinkedList(CreateLinkedList(new List<int>(){ 2, 44, 7 }));

        //PrintLinkedList(DuplicateRemoval(CreateLinkedList(new List<int>(){ 2, 4, 7 })));

        //PrintLinkedList(DuplicateRemoval(CreateLinkedList(new List<int>(){ 7 })));

        //PrintLinkedList(DuplicateRemoval(CreateLinkedList(new List<int>(){ 2, 2, 7 })));

        //PrintLinkedList(DuplicateRemoval(CreateLinkedList(new List<int>(){ 2, 7, 7, 3 })));

        //PrintLinkedList(DuplicateRemoval(CreateLinkedList(new List<int>(){ 2, 2 })));

        //PrintLinkedList(DuplicateRemoval(CreateLinkedList(new List<int>(){ 2, 7, 7, 2 })));

        //PrintLinkedList(DuplicateRemoval(CreateLinkedList(new List<int>(){ 2, 4, 7, 55, 7, 8, 7, 22, 4, 11, 9 })));

        //PrintLinkedList(KthToLast(4, CreateLinkedList(new List<int>(){ 2, 4, 7, 55, 7, 8, 7, 22, 4, 11, 9 })));

        //PrintLinkedList(KthToLast(4, CreateLinkedList(new List<int>(){ 2, 4, 7, 9 })));

        Node linkedList = new Node(4);

        linkedList.Next = new Node(3);

        linkedList.Next.Next = new Node(5);

        DeleteMiddleNode(linkedList.Next);

        PrintLinkedList(linkedList);

        // Console.WriteLine(linkedList.Next.Data);

        // Console.WriteLine(linkedList.Next.Next.Next == null);

        Console.WriteLine("Hello World");

    }

}