using System;

public class Program

{

    public static void Main()

    {

        var a = new ListNode<string>("a", new ListNode<string>("b", new ListNode<string>("c", null)));

        var e = new ListNode<string>("e", new ListNode<string>("f", new ListNode<string>("g", null)));

​

        var resultForCombine = ListNode<string>.CombineListNode(a, e);

​

        var res = resultForCombine;

        Console.WriteLine("Test combine");

        while (true)

        {

            Console.WriteLine(res.Value);

            if (res.Next == null) break;

            res = res.Next;

​

        }

        var o = new ListNode<string>("o", null);        

        var resForReplace = ListNode<string>.ReplaceListNode(resultForCombine, e, o);

        res = resForReplace;

        Console.WriteLine("Test replace");

        while (true)

        {

            Console.WriteLine(res.Value);

            if (res.Next == null) break;

            res = res.Next;

​

        }

    }

    class ListNode<T>

    {

        public readonly T Value;

        public readonly ListNode<T> Next;

​

        public ListNode(T value, ListNode<T> next)

        {

            Value = value;

            Next = next;

        }

        public static ListNode<T> ReplaceListNode(ListNode<T> source, ListNode<T> search, ListNode<T> replace)

        {           

            if(source == null) return null;

            if(source.Equals(search))

            {

                if(source.Next == null)

                    return replace;

                return CombineListNode(replace, source.Next);

            }

            if(source.Next == null)

                return null;

            return new ListNode<T>(source.Value, ReplaceListNode(source.Next, search, replace));

        }

​

        public static ListNode<T> CombineListNode(ListNode<T> first, ListNode<T> second)

        {

            if(first.Next == null)

                return new ListNode<T>(first.Value, second);

​

            return new ListNode<T>(first.Value, CombineListNode(first.Next, second));

        }

    }

}