using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Stack <T>
    {
        private node<T> First;
        public Stack()
        {
            First = null;
        }
        public bool IsEmpty()
        {
            if (First != null)
                return false;
            return true;
        }
        public T Top()
        {
            return this.First.GetValue();
        }
        public string ToString()
        {
            string s = "";
            while (First != null)
            {
                s = s + First.GetValue();
                if (First.GetNext() != null)
                {
                    First = First.GetNext();
                    s = s + " , ";
                }
            }
            return s;
        }
        public void Push(T x)
        {
            if (this.Top() == null)
                First.SetValue(x);
            node<T> s = new node<T>(x, First);
            s = First;
        }
        public T Pop()
        {
                node<T> x = First;
                First = null;
                return x.GetValue();
        }
    }
    class node<T>
    {
        private T Value;
        private node<T> next;
        public node(T X)
        {
            this.Value = X;
            this.next = null;
        }
        public node(T X, node<T> next)
        {
            this.Value = X;
            this.next = next;
        }
        public T GetValue()
        {
            return this.Value;
        }
        public node<T> GetNext()
        {
            return this.next;
        }
        public void SetValue(T x)
        {
            this.Value = x;
        }
        public void SetNext(node<T> next)
        {
            this.next = next;
        }
        public bool HasNext()
        {
            if (this.next == null)
            {
                return false;
            }
            return true;
        }
        public override string ToString()
        {
            return "(the value is " + this.Value + ")";
        }
        static public bool Alef1(node<T> P, T n)
        {
            while (P != null)
            {
                if (n.Equals(P.GetValue()))
                {
                    P = P.GetNext();
                    return true;
                }
                P = P.GetNext();
                return false;
            }
            if (n.Equals(P.GetValue()))
                return true;
            return false;
        }
        static public int Bet1(node<T> P, T n)
        {
            int counter = 0;
            while (P != null)
            {
                if (n.Equals(P.GetValue()))
                    return counter;
                else
                {
                    counter++;
                    P = P.GetNext();
                }
            }
            return -1;
        }
        static public void Gimel1(node<T> P, T n, T x)
        {
            if (Alef1(P, n))
            {
                int place = Bet1(P, n);
                for (int i = 0; i < place; i++)
                {
                    P = P.GetNext();
                }
                P.SetValue(x);
            }
        }
        static public int GetLength(node<T> P)
        {
            int i = 0;
            while (P != null)
            {
                i++;
                P = P.GetNext();
            }
            return i;
        }
        static public void Delete(node<T> P, int n)
        {
            while (P != null)
            {
                if (P.GetNext().GetValue().Equals(n))
                    P.SetNext(P.GetNext().GetNext());
            }
        }
        static public void Change(node<T> P, int n)//O(n)
        {
            T value; T value1;
            for (int i = 0; i < n; i++)
            {
                P = P.GetNext();
            }
            value = P.GetValue();
            value1 = P.GetNext().GetValue();
            P.SetValue(value1);
            P.GetNext().SetValue(value);
        }
        public static void connect(node<T> P, node<T> M)
        {
            while (P.GetNext() != null)
            {
                P = P.GetNext();
            }
            P.GetNext().SetNext(M);
        }
        public static node<T> Q5(node<T> P, node<T> M)
        {
            if (P == null)
                return M;
            if (M == null)
                return P;
            node<T> mrgList;
            if (P.GetValue() < M.GetValue())
            {
                mrgList = P;
                P = P.GetNext();
            }
            else
            {
                mrgList = M;
                M = M.GetNext();
            }
            node<T> posMrg = mrgList;
            while (P != null && M != null)
            {
                if (P.GetValue() < M.GetValue())
                {
                    posMrg.SetNext(P);
                    P = P.GetNext();
                }
                else
                {
                    posMrg.SetNext(M);
                    M = M.GetNext();
                }
                posMrg = posMrg.GetNext();
            }
            while (P != null)
            {
                posMrg.SetNext(P);
                P = P.GetNext();
                posMrg = posMrg.GetNext();
            }
            while (M != null)
            {
                posMrg.SetNext(M);
                M = M.GetNext();
                posMrg = posMrg.GetNext();
            }
            return mrgList;
        }
        public static node<T> Q6(node<T> P, node<T> M)
        {
            {
                if (P == null || M == null)
                    return null;
                node<T> cutList;
                while (P != null && M != null)
                {
                    if (P.GetValue().Equals(M.GetValue()))
                    {
                        cutList = P.GetValue();
                        P = P.GetNext();
                        M = M.GetNext();
                    }
                }
                return cutList.GetNext();
            }

        }
    }
    class Program
    {


        static public node<int> shirsore(node<int> p, node<int> p1)
        {
            node<int> l = p;
            while (p != null)
            {
                p = p.GetNext();
            }
            p.SetNext(p1);
            return l;
        }
        static public void print(node<int> p)
        {
            if (p == null) return;
            while (p != null)
            {
                Console.WriteLine(p.ToString());
                p = p.GetNext();
            }
        }
        static void Main(string[] args)
        {
            node<int> p = new node<int>(4);
            node<int> p1 = new node<int>(2, p);
            node<int> p2 = new node<int>(8, p1);
        }
    }
}