using System;

public class Program

{

    public static Node root = null;

    public static void Main()

    {

        int j = 9;

        Console.WriteLine(j%10);

        //Console.WriteLine("\t\t\tOriginal Linked List\n");        

        //Print(root);

        root = Add(root, 1);

        root = Add(root, 2);

        root = Add(root, 3);

        root = Add(root, 4);

        root = Add(root, 5);

        Console.WriteLine("\n\n\t\t\tOriginal Linked List\n");      

        Print(root);

        Console.Write("null");

        Node first = null, second = null;

        first = Add(first, 7);

        first = Add(first, 1);

        first = Add(first, 6);

        //first = Add(first, 3);

        second = Add(second, 9);

        second = Add(second, 9);

        second = Add(second, 9);

        second = Add(second, 9);

        Console.WriteLine("\n\n\t\t\tAddition(Iteration) Linked List \n");      

        Print(first);

        Console.WriteLine("null");

        Print(second);

        Console.WriteLine("null");

        AdditionIterative(first, second);

​

        Node sum = AdditionRecursive(first, second, null, 0);

        Console.Write("\n\n\t\tSUM : ");

        while(sum!=null)

        {

            Console.Write(sum.Value + " -> ");          

            sum = sum.Next;

        }

        Console.WriteLine("null");

        second = Add(second, 9);

        second = Add(second, 9);

        Console.WriteLine("\n\n\t\t\tAddition Different Size (Iteration) Linked List \n");  

        AdditionDifferntSizeIteration(first, second);

        Reverse();

        Console.WriteLine("\n\n\t\t\tReverse(Iteration) Linked List \n");       

        Print(root);

        Console.Write("null");

        ReverseRec(root);

        Console.WriteLine("\n\n\t\t\tReverse(Recursive) Linked List \n");       

        Print(root);

        Console.Write("null");

        DeleteModdleItem();

        Console.WriteLine("\n\n\t\t\tDelete Middle Item from Linked List \n");      

        Print(root);

        Console.Write("null");

    }

    public static void AdditionIterative(Node first, Node second){

        int c =0;

        Node addition = null, n = null;;

        Node temp = addition;

        while(first != null && second != null){

            int sum = first.Value + second.Value + c;

            n = new Node(sum%10);

            c = sum/10;             

            if(addition == null){

                addition = n;

                temp = n;

            }

            else{

                addition.Next = n;          

                addition = n;

            }

            first = first.Next;

            second = second.Next;

        }

        if(c > 0){

            n = new Node(c);

            addition.Next = n;

        }

        Console.Write("\n\n\t\tSUM : ");

        while(temp!=null)

        {

            Console.Write(temp.Value + " -> ");         

            temp = temp.Next;

        }

        Console.WriteLine("null");

    }

    public static Node AdditionRecursive(Node first, Node second, Node sum, int c){

        Node n = null;

        if(first != null && second != null){

            int v = first.Value + second.Value + c;         

            n = new Node(v%10);                 

            c = v/10;

            if(sum == null){

                sum = n;

            }else{

                sum.Next = n;               

            }

            AdditionRecursive(first.Next, second.Next, n, c);

        }else{

            if(c >0){

                n = new Node(c);

                if(sum == null){

                    sum = n;

                }else{

                    sum.Next = n;               

                }

            }

        }

        return n;

    }

    public static int carry = 0;

    public static void AdditionDifferntSizeIteration(Node first, Node second){

        int firstLen = GetLength(first);

        int secondLen = GetLength(second);

        Console.WriteLine("\nfirst length = {0}\tsecond length = {1}", firstLen, secondLen);

        first = PadZeros(first, secondLen - firstLen);

        second = PadZeros(second, firstLen - secondLen);

        Print(first);

        Console.WriteLine("null");

        Print(second);

        Console.WriteLine("null");

        Node sum = Addition(first, second, null);

        if(carry > 0){

            Node n = new Node(carry);

            n.Next = sum;

            sum = n;            

        }

        Print(sum);

        Console.WriteLine("null");

    }

    public static Node Addition(Node n1, Node n2, Node sum){

        if(n1 != null && n2 != null){

            sum = Addition(n1.Next, n2.Next, sum);

            int s = n1.Value + n2.Value + carry;

            Node n = new Node(s%10);

            carry = s/10;

            n.Next = sum;

            sum = n;

        }

        return sum;

    }

    public static Node PadZeros(Node node, int diff){

        for(;diff >0 ; diff--){

            Node n = new Node(0);

            n.Next = node;

            node = n;

        }

        return node;

    }

    public static int GetLength(Node node){

        int i =0;

        while(node != null){                    

            node = node.Next;

            i++;            

        }

        return i;       

    }

​

    public static Node Add(Node root, int val){

        Node node = new Node(val);

        if(root == null)

            return node;

        Node head = root;

        while(head!=null){

            if(head.Next == null){

                head.Next = node;

                break;

            }

            head = head.Next;           

        }

        return root;

    }

    public static void Print(Node node){

        if(node != null){

            Console.Write(node.Value + " -> ");

            Print(node.Next);

        }

    }

    public static void DeleteModdleItem(){

    }

    public static void Reverse(){

    }

    public static void ReverseRec(Node node){

    }   

​

​

}

​

public class Node {

​

    public int Value{get;set;}

    public Node Next{get;set;}  

    public Node(int v){

        Value = v;

        Next = null;

    }

}