Exam

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

namespace Linked_List_Sort
{
    class Program
    {



        /* Link list node */
        public class Node
        {
            public int data;
            public Node next;
            public Node(int d)
            {
                data = d;
                next = null;
            }
        }

        public class MergeLists
        {
            Node head;

            /* Method to insert a node at
            the end of the linked list */
            public void addToTheLast(Node node)
            {
                if (head == null)
                {
                    head = node;
                }
                else
                {
                    Node temp = head;
                    while (temp.next != null)
                        temp = temp.next;
                    temp.next = node;
                }
            }

            /* Method to print linked list */
            void printList()
            {
                Node temp = head;
                while (temp != null)
                {
                    Console.Write(temp.data + " ");
                    temp = temp.next;
                }
                Console.WriteLine();
                Console.ReadLine();
            }


            // Driver Code
            public static void Main(String[] args)
            {
                /* Let us create two sorted linked
                lists to test the methods
                Created lists:
                    Head1: 4, 8, 15, 19
                    Head2: 7, 9, 10, 16
                */
                MergeLists Head1 = new MergeLists();
                MergeLists Head2 = new MergeLists();

                
                Head1.addToTheLast(new Node(4));
                Head1.addToTheLast(new Node(8));
                Head1.addToTheLast(new Node(15));
                Head1.addToTheLast(new Node(19));
               
                 
                Head2.addToTheLast(new Node(7));
                Head2.addToTheLast(new Node(9));
                Head2.addToTheLast(new Node(10));
                Head2.addToTheLast(new Node(16));
                

                Head1.head = new Gfg().sortedMerge(Head1.head,
                                                Head2.head);
                Head1.printList();

            }
        }

        public class Gfg
        {
            /* Takes two lists sorted in
            increasing order, and splices
            their nodes together to make
            one big sorted list which is
            returned. */
            public Node sortedMerge(Node headA, Node headB)
            {

                /* a dummy first node to
                hang the result on */
                Node dummyNode = new Node(0);

                /* tail points to the
                last result node */
                Node tail = dummyNode;
                while (true)
                {

                    /* if either list runs out,
                    use the other list */
                    if (headA == null)
                    {
                        tail.next = headB;
                        break;
                    }
                    if (headB == null)
                    {
                        tail.next = headA;
                        break;
                    }

                    /* Compare the data of the two
                    lists whichever lists' data is
                    smaller, append it into tail and
                    advance the head to the next Node
                    */
                    if (headA.data <= headB.data)
                    {
                        tail.next = headA;
                        headA = headA.next;
                    }
                    else
                    {
                        tail.next = headB;
                        headB = headB.next;
                    }

                    /* Advance the tail */
                    tail = tail.next;
                }
                return dummyNode.next;
            }
        }
    }
          
}