Introduction

Sum of two linked lists without any extra space and modification to the Linked List.

Input:
N = 2
valueN[] = {4,5}
M = 3
valueM[] = {3,4,5}
Output: 3 9 0  
Explanation: For the given two linked
list (4 5) and (3 4 5), after adding
the two linked list resultant linked
list will be (3 9 0).

Input:
N = 2
valueN[] = {6,3}
M = 1
valueM[] = {7}
Output: 7 0
Explanation: For the given two linked
list (6 3) and (7), after adding the
two linked list resultant linked list
will be (7 0).

Approach

The suggested approach is to use the recursion and have the carry returned from each recursion and a result linked list populated in the process. We can calculate the size of the list and recurse with the size in mind because the addition should start where the elements size is same and carry should continue further up.

using System;

namespace PracticeSucks
{
    class Node
    {
        public int Data;
        public Node Next;

        public Node(int d)
        {
            Data = d;
            Next = null;
        }
    }
    public static class Program
    {
        private static void Main()
        {
            var a = new Node(7) { Next = new Node(7) { Next = new Node(0) { Next = new Node(3) { Next = new Node(2) } } } };
            var b = new Node(2) { Next = new Node(9) { Next = new Node(6) { Next = new Node(6) { Next = new Node(0) } } } };
            var c = AddLists(a, b);
            Console.WriteLine();
            while (c != null)
            {
                Console.Write(c.Data + " ");
                c = c.Next;
            }
            Console.WriteLine();
        }

        private static Node AddLists(Node first, Node second)
        {
            // code here
            var firstSize = GetSize(first);
            var secondSize = GetSize(second);

            var start = new Node(-1);

            // Make sure that the second array is the greater in size always
            var carry = firstSize > secondSize
                ? AddListsUtil(second, secondSize, first, firstSize, start)
                : AddListsUtil(first, firstSize, second, secondSize, start);

            var result = start.Data == -1 ? start.Next : start;
            if (carry <= 0)
            {
                return result;
            }

            var temp = new Node(carry) { Next = result };
            result = temp;

            // return head of sum list
            return result;
        }

        // Uses recursion
        private static int AddListsUtil(Node first, int firstSize, Node second, int secondSize, Node result)
        {
            if (first == null || second == null || firstSize == 0 || secondSize == 0)
            {
                return 0;
            }
            if (firstSize != secondSize)
            {
                // It will use the carry and the second array
                var localNext = new Node(-1);
                var localCarry = AddListsUtil(first, firstSize, second.Next, secondSize - 1, localNext);
                // Indicates no local data found
                if (localNext.Data == -1)
                {
                    return localCarry;
                }
                result.Next = localNext;
                var retLocal = (second.Data + localCarry) / 10;
                result.Data = (second.Data + localCarry) % 10;

                return retLocal;
            }

            var next = new Node(-1);
            var carry = AddListsUtil(first.Next, firstSize - 1, second.Next, secondSize - 1, next);
            // Indicates no local data found
            if (firstSize > 1)
            {
                result.Next = next;
            }
            result.Data = first.Data + second.Data;
            var ret = (result.Data + carry) / 10;
            result.Data = (result.Data + carry) % 10;
            return ret;
        }

        private static int GetSize(Node node)
        {
            int size = 0;
            while (node != null)
            {
                size++;
                node = node.Next;
            }
            return size;
        }
    }
}