using System;

//using System.Linq;

using System.Collections;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        LinkedList<int> linkedList = new LinkedList<int>();

        // добавление элементов

        /*linkedList.Add("Tom");

        linkedList.Add("Alice");

        linkedList.Add("Bob");

        linkedList.Add("Sam");

        linkedList.Add("Dan");

        */

        linkedList.Add(1);

        linkedList.Add(2);

        linkedList.Add(3);

        linkedList.Add(4);

        linkedList.Add(5); 

        // выводим элементы

        foreach(var item in linkedList.Reverse())

        {

            Console.WriteLine(item);

        }

        Console.WriteLine();

        foreach(var item in linkedList.ReverseUsingRecursion())

        {

            Console.WriteLine(item);

        }

    }

}

​

public static class MyLinq

{

​

    public static LinkedList<T> Reverse<T>(this LinkedList<T> linkedList){

        var head = linkedList.First;

        while (head.Next != null)

        {

            var next = head.Next;

            linkedList.Remove(next.Data);

            linkedList.AppendFirst(next.Data);

        }

        return linkedList;

    }

    public static LinkedList<T> ReverseUsingRecursion<T>(this LinkedList<T> linkedList)

    {

        var head = linkedList.First;

        if (head == null) return new LinkedList<T>();

        if (head.Next == null)

        {

            var newLinkedList = new LinkedList<T>();

            newLinkedList.AppendFirst(head.Data);

            return newLinkedList;

        }

        linkedList.Remove(head.Data);

        linkedList.ReverseUsingRecursion();

        head.Next.Next = head;

        head.Next = null;

        return linkedList;

    }

​

}

​

​

public class Node<T>

{

    public Node(T data)

    {

        Data = data;

    }

    public T Data { get; set; }

    public Node<T> Next { get; set; }

}

​

public class LinkedList<T> : IEnumerable<T>  // односвязный список

    {

        Node<T> head; // головной/первый элемент

        Node<T> tail; // последний/хвостовой элемент

        int count;  // количество элементов в списке

        // добавление элемента

        public void Add(T data)

        {

            Node<T> node = new Node<T>(data);

            if (head == null)

                head = node;

            else

                tail.Next = node;

            tail = node;

            count++;

        }

        // удаление элемента

        public bool Remove(T data)

        {

            Node<T> current = head;

            Node<T> previous = null;

            while (current != null)

            {

                if (current.Data.Equals(data))

                {

                    // Если узел в середине или в конце

                    if (previous != null)

                    {

                        // убираем узел current, теперь previous ссылается не на current, а на current.Next

                        previous.Next = current.Next;

                        // Если current.Next не установлен, значит узел последний,

                        // изменяем переменную tail

                        if (current.Next == null)

                            tail = previous;

                    }

                    else

                    {

                        // если удаляется первый элемент

                        // переустанавливаем значение head

                        head = head.Next;

                        // если после удаления список пуст, сбрасываем tail

                        if (head == null)

                            tail = null;

                    }

                    count--;

                    return true;

                }

                previous = current;

                current = current.Next;

            }

            return false;

        }

        public Node<T> First { get { return head; } }

        public Node<T> Last { get { return tail; } }

        public int Count { get { return count; } }

        public bool IsEmpty { get { return count == 0; } }

        // очистка списка

        public void Clear()

        {

            head = null;

            tail = null;

            count = 0;

        }

        // содержит ли список элемент

        public bool Contains(T data)

        {

            Node<T> current = head;

            while (current != null)

            {

                if (current.Data.Equals(data))

                    return true;

                current = current.Next;

            }

            return false;

        }

        // добвление в начало

        public void AppendFirst(T data)

        {

            Node<T> node = new Node<T>(data);

            node.Next = head;

            head = node;

            if (count == 0)

                tail = head;

            count++;

        }

        // реализация интерфейса IEnumerable

        IEnumerator IEnumerable.GetEnumerator()

        {

            return ((IEnumerable)this).GetEnumerator();

        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()

        {

            Node<T> current = head;

            while (current != null)

            {

                yield return current.Data;

                current = current.Next;

            }

        }

    }