using System;

/// <summary>

    /// Leetcode 2 - Add two numbers

    ///  - https://leetcode.com/problems/add-two-numbers/ 

    /// 

    /// NOTE:

    /// -  lists may be of diff sizes: e.g. [1->1->1] + [2] or [1->1->1] + [2->2]

    /// - if the numbers are stored in a reverse order, that is good

    ///     - we operate from right to left

    ///     

    /// - we have to make sure number at the same place values

    ///  e.g: [1 -> 2 -> 3] is number 321, [2 -> 7] is number 72

    ///  

    /// ones   tens   hundreds

    ///  1 ->  2   ->   3

    ///        7   ->   2

    /// 

    /// - once this is setup correctly, the operation is easy

    /// -  need head and tail,

    /// - since we are adding at the end, tail will keep moving

    /// - head stays the same(i.e first number added stays first)

    /// - at the end we return head (reference to the first element)

    ///

    /// Main operations:

    ///  1. 

    ///   - first create a first node and set head and tail to it

    ///   - now begin a while loop till one of the list is done

    ///  

    ///   - (la.val + l2.val + carryover) % 10 = the value at the current location, i.e new node

    ///   - (la.val + l2.val + carryover) / 10 = the cary over, since this is base 10 decimals, 

    ///     and we are adding single digits, this value is either 0 or 1, this becomes the new node

    ///     

    ///   - when new node is created, it goes to the end

    ///    1) tail.next = newNode; // the current tail now has a next

    ///    2) tail = newNode;      // the new node then becomes the tail

    ///    

    /// 2. loop till one of the lists ends

    /// 

    /// 3.

    ///   - when the loop ends, peform while loop mto add any remaining numbers, only one list will have elments remaining

    /// 

    /// 4.

    ///   - the addition of all the numbers can create a new place value e.g. from 10 to 100, iof that bhappens there will be a remainder

    ///   - check and add one last node

    ///  

    ///  2) sum each column

    ///  3) perform a mod 10 to get remainder, remainder stays in this current columm

    ///  4) perform a divide to get carry over, store the carry over for next step

    ///  

    /// </summary>

​

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Linked list 1: [3,4,2] stored in reverse order");

        // number stored in reverse

        // [2,4,3]

        ListNode l0 = new ListNode(3);

        ListNode l1 = new ListNode(4, l0);

        ListNode l2 = new ListNode(2, l1);

        ListNode.Print(l2);

​

        Console.WriteLine("Linked list 2: [4,6,5] stored in reverse order");

        // [4,6,5]

        ListNode l6 = new ListNode(4);

        ListNode l7 = new ListNode(6, l6);

        ListNode l8 = new ListNode(5, l7);

        ListNode.Print(l8);

​

        ListNode l =  Program.AddTwoNumbers(l2,l8);

​

        Console.WriteLine("Results");

        ListNode.Print(l);

    }

  public static ListNode AddTwoNumbers(ListNode l1, ListNode l2) {

​

        ListNode l = l1, r = l2;

        ListNode head = new ListNode((l.val + r.val) % 10);

        ListNode tail = head;

        int remainder = (l.val + r.val) / 10;

        // move forward in the list

        l = l.next;

        r = r.next;

        // case where lists are same length

        while ( l != null && r != null)

        {

            // this is going to the end of the list

            tail.next = new ListNode((l.val + r.val + remainder) % 10);

            tail = tail.next;

            remainder = (l.val + r.val + remainder) / 10;

​

            // move forward 

            l = l.next;

            r = r.next;

        }

        // did one of the list end?

        while (l != null)

        {

            tail.next = new ListNode((l.val + remainder) % 10);

            tail = tail.next;

            remainder = (l.val + remainder) / 10;

            l = l.next;

        }

        while (r != null)

        {

            tail.next = new ListNode((r.val + remainder) % 10);

            tail = tail.next;

            remainder = (r.val + remainder) / 10;

            r = r.next;

        }

​

        // if there is a remainder, it will be a 1 and a new node is needed at the end

        if (remainder>0)

        {

            tail.next = new ListNode(1);

        }

​

        return head;

   }

}

​

///////////////////////////////

// list node

//////////////////////////////

// FILO

public class ListNode

{

    public int val;

    public ListNode next;

    public ListNode()

    {

    }

    public ListNode(int _val, ListNode _next = null)

    {

        this.val = _val;

        this.next = _next;

    }

​

    public static void Print(ListNode node)

    {

        while(node!=null)

        {

            Console.WriteLine(node.val);

            node = node.next;

        }

    }

}