using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        Node head=InitLL("int");

        Node head2=InitLL("int");

        //Simple Linked List Traversal

        PrintLL(head);

        //PrintLLRec(head2);

        //Put elements of a linked list in an array/List

        //List<int> op=ReturnElements(head);

        //op=ReturnElementsRec(head);

        //PrintList(op);

        //Sum of all elements in the list

        //int sum=SumList(head);

        //Console.WriteLine(sum);

        //sum=SumListRec(head);

        //Console.WriteLine(sum);

        //Return if a given value is present in the Linked List

        //Console.WriteLine(FindInLL(head,10));

        //Console.WriteLine(FindInLLRec(head,10));

        //Given a Linked List and an index value, return the element at that index

        //Console.WriteLine(GetNodeVal(head,8));

        //Console.WriteLine(GetNodeValRec(head,1));

        //Reverse LL

        //VVIP --> ReverseLLRec

        Node rev=ReverseLL(head);

        PrintLL(rev);

        //Node rev=ReverseLLRec(head,null);

        //PrintLL(rev);

        // Zip zap 2 lists

        //Given 1-->2-->3-->4-->5-->NULL AND 6-->7-->8-->NULL, return 1-->6-->2-->7-->3-->8-->4-->5-->NULL

        //Node zip=ZapList(head,head2);

        //PrintLL(zip);

    }

    public class Node

    {

        public int value;

        public Node next;

        public Node (int x)

        {

            value=x;

            next=null;

        }

    }

    public static void PrintLL(Node head)

    {

        while(head!=null)

        {

            Console.WriteLine(head.value.ToString());

            head=head.next;

        }

    }

    public static void PrintLLRec(Node head)

    {

        if(head==null) return;

        Console.WriteLine(head.value.ToString());

        PrintLLRec(head.next);

    }

    public static Node ZapList(Node head1,Node head2)

    {

        Node tail=head1;

        Node curr1=head1.next;

        Node curr2=head2;

        int cnt=0;

        while(curr1!=null && curr2!=null)

        {

            if(cnt%2==0)

            {

                tail.next=curr2;

                curr2=curr2.next;

            }

            else

            {

                tail.next=curr1;

                curr1=curr1.next;

            }

            tail=tail.next;

            cnt++;

        }

        if(curr1==null)

            tail.next=curr1;

        else if(curr2==null)

            tail.next=curr2;

        return head1;

    }

    public static Node ReverseLL(Node head)

    {

        //Node headO=new Node();

        //HEAD 1-->2-->3-->4-->5-->NULL

        //PREV 5-->4-->3-->2-->1-->NULL

        //Node curr=head;

        Node prev=null;

        while(head!=null)

        {

            Node next=head.next;

            head.next=prev;

            prev=head;

            head=next;

        }

        return prev;

    }

    public static Node ReverseLLRec(Node head,Node prev)

    {

        if(head==null) return prev;

        Node next=head.next;

        head.next=prev;

        return ReverseLLRec(next,head);

    }

    public static bool FindInLL(Node head,int val)

    {

        while(head!=null)

        {

            if(head.value==val) return true;

            head=head.next;

        }

        return false;

    }

    public static bool FindInLLRec(Node head,int val)

    {

        if(head==null) return false;

        if(head.value==val) return true;

        return FindInLLRec(head.next,val);

    }

    public static int GetNodeVal(Node head,int indx)

    {

        int curr=0;

        while(head!=null)

        {

            if(indx==curr)

                return head.value;

            curr++;

            head=head.next;

        }

        return Int32.MinValue;

    }

    public static int GetNodeValRec(Node head,int indx)

    {

        if(indx==0) return head.value;

        if(head==null) return Int32.MinValue;

        return GetNodeValRec(head.next,indx-1);

    }

    public static int SumList(Node head)

    {

        //has O(1) space complexity and O(n) time complexity

        int sum=0;

        while(head!=null)

        {

            sum+=head.value;

            head=head.next;

        }

        return sum;

    }

    public static int SumListRec(Node head)

    {

        //has O(n) space and time complexity

        if(head==null) return 0;

        return head.value+SumListRec(head.next);

    }

    public static List<int> ReturnElements(Node head)

    {

        List<int> output=new List<int>();

        while(head!=null)

        {

            output.Add(head.value);

            head=head.next;

        }

        return output;

    }

    public static List<int> ReturnElementsRec(Node head)

    {

        if(head==null) return null;

        List<int> output=new List<int>();

        output.Add(head.value);

        List<int> temp=ReturnElementsRec(head.next);

        if(temp!=null)

            output.AddRange(temp);

        return output;

    }

    public static void PrintList(List<int> input)

    {

        foreach(int i in input)

        {

            Console.WriteLine(i.ToString());

        }

    }

    public static Node InitLL(string dt)

    {

        if(dt=="int")

        {

            Node head=new Node(1);

            Node one=new Node(2);

            Node two=new Node(3);

            Node three=new Node(4);

            Node four=new Node(5);

            head.next=one;

            one.next=two;

            two.next=three;

            three.next=four;

            return head;

        }

        else

        {

            Node head=new Node(Int32.MinValue);

            return head;

        }

    }

}