Adding two linked lists and outputting the result in a new linked list discussion in javascript

Question

Question:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Suggested Solution:

function ListNode(val) {
  this.val = val;
  this.next = null;
}

// adding two Linked Lists.
var addTwoNumbers = function(l1, l2) {
 const temp = new ListNode(0);
 let resultPointer = temp;
 var digit = 0;
 var carryover = 0;
 while(
   l1!== null ||
   l2 !== null
  ){
    var sum = 0;
    if(l1!== null){
      sum += l1.val;
      l1 = l1.next;           
    }

    if(l2!== null){
      sum += l2.val;
      l2 = l2.next;
    }

    sum = sum + carryover;
    carryover = sum >= 10 ? 1 : 0;
    resultPointer.next = new ListNode(sum % 10);
    resultPointer = resultPointer.next;
 }
  return temp.next;    
};

Output: [7,0,8];

Why does the following change outputs an [] list.

       let resultPointer = new ListNode(0);
       return resultPointer.next();

Any Suggestions would be helpful.

Answer 1

Hope this can help someone in c#

class Node {
    public int data_ { get; set; }

    public Node next;

    public Node(int data)
    {
        data_ = data; 
    }
}

class LinkedList
{

    public Node AddLinkedListData(Node n1, Node n2)
    {

        Node temp = new Node(0);
        Node Finalresult = temp;
        int carryover = 0;
        int sum = 0;

        while (n1 != null || n2 != null || carryover != 0 )
        {
            sum = carryover;

            if(n1 != null)
            {
                sum += n1.data_;
                n1 = n1.next;
            }

            if(n2 != null)
            {
                sum += n2.data_;
                n2 = n2.next; 
            }

            carryover = sum / 10;

            Finalresult.next = new Node(sum % 10);
           Finalresult = Finalresult.next; 

        }
        return temp.next;
    }


    public Node reverseLinkedList(Node temp)
    {
        Node prev = null;
        Node current = temp;
        while(current != null)
        {
            Node next = current.next;
            current.next = prev;
            prev = current;
            current = next; 

        }
        return prev; 

    }
}

**Then on your main, You can debug or display both list **

    class Program{

    static void Main(){
        Node node = new Node(3);
        node.next = new Node(4);
        node.next.next = new Node(2);

        Node node1 = new Node(4);
        node1.next = new Node(6);
        node1.next.next = new Node(5);

       LinkedList list = new LinkedList();

       Node AddedList =  list.AddLinkedListData(node, node1);

        Console.WriteLine("Unreversed List ......");

        Node OriginaList = AddedList;

        while(OriginaList != null)
        {
            Console.WriteLine(OriginaList.data_);
            OriginaList = OriginaList.next; 
        }


        Node reverseList = list.reverseLinkedList(AddedList);

        Node NodetoDisplay = reverseList;

        Console.WriteLine("Reversed List ......");

        while (NodetoDisplay != null)
        {
            Console.WriteLine(NodetoDisplay.data_);
            NodetoDisplay = NodetoDisplay.next; 
        }

        
    }
}

Answer 2

I come up with this code for this program using Queues, Hope this helps someone

// C# program to add two numbers represented by Linked
// Lists using Queues
using System;
using System.Collections.Generic;
public class List
{

    public class Node
    {

        public int data;
        public Node next;

        public Node(int d)
        {
            data = d;
            next = null;
        }
    }

    public static Node head1, head2;
    // function that calculates and prints the sum of two
    // numbers represented by linked lists
    public void addTwoLists(Node l1, Node l2)
    {
        Node prev = null;
        // Create 3 Queues
        Queue<Node> q1 = new Queue<Node>();
        Queue<Node> q2 = new Queue<Node>();
        Queue<Node> q3 = new Queue<Node>();
        // Fill first Queue with first List Elements
        while (l1 != null)
        {
            q1.Enqueue(l1);
            l1 = l1.next;
        }
        // Fill second Queue with second List Elements
        while (l2 != null)
        {
            q2.Enqueue(l2);
            l2 = l2.next;
        }
        int carry = 0;
        // Fill the third Queue with the sum of first and second Queues
        while (q1.Count != 0 && q2.Count != 0)
        {
            int sum
                = q1.Peek().data + q2.Peek().data + carry;
            Node temp = new Node(sum % 10);
            q3.Enqueue(temp);
            if (sum > 9)
            {
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            q1.Dequeue();
            q2.Dequeue();
        }
        while (q1.Count != 0)
        {
            int sum = carry + q1.Peek().data;
            Node temp = new Node(sum % 10);
            q3.Enqueue(temp);
            if (sum > 9)
            {
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            q1.Dequeue();
        }
        while (q2.Count != 0)
        {
            int sum = carry + q2.Peek().data;
            Node temp = new Node(sum % 10);
            q3.Enqueue(temp);
            if (sum > 9)
            {
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            q2.Dequeue();
        }
        // If carry is still present create a new node with
        // value 1 and Enqueue it to the third Queue
        if (carry == 1)
        {
            Node temp = new Node(1);
            q3.Enqueue(temp);
        }
        // Link all the elements inside third Queue with
        // each other
        if (q3.Count != 0)
            prev = q3.Peek();
        while (q3.Count != 0)
        {
            Node temp = q3.Peek();
            q3.Dequeue();
            if (q3.Count == 0)
            {
                temp.next = null;
            }
            else
            {
                temp.next = q3.Peek();
            }
        }
        printList(prev);
    }

    /* Utility function to print a linked list */
    public void printList(Node head)
    {
        while (head.next != null)
        {
            Console.Write(head.data + " -> ");
            head = head.next;
        }
        Console.WriteLine(head.data);
    }

    public static void Main(String[] args)
    {
        List list = new List();

        // creating first list
        Node head1 = new Node(2);
        head1.next = new Node(4);
        head1.next.next = new Node(3);
        Console.Write("First List : ");
        list.printList(head1);

        // creating second list
        Node head2 = new Node(5);
        head2.next = new Node(6);
        head2.next.next = new Node(4);        
        Console.Write("Second List : ");
        list.printList(head2);

        Console.Write("Resultant List : ");
        // add the two lists and see the result
        list.addTwoLists(head1, head2);
    }
}

Answer 3

NB: It's not an answer!

There's something wrong on your code; you should add another dimension, otherwise when you have carryover after adding last digit, it will give wrong result;

9 8

2 2

Result: 20

For, over coming this wrongness, you have to add the last carryOver at the list;

if((sum/10) !== 0){
      resultPointer.next = new ListNode(sum / 10);
      resultPointer = resultPointer.next;
}

this will add the last carryOver in the list;

Answer 4

When you declare

let resultPointer = new ListNode(0);

It creates a new linked list. It doesn't have any connection whatsoever with temp. Then after the execution of while loop, your resultPointer points to the last entry of that list and it doesn't have any linked list further to that pointer. So when you return resultPointer.next() - it's actually an empty list.

On the contrary - in your suggested solution, temp is actually the head of the linked list. For iteration - it uses the resultPointer. So even after executing the while loop, temp is still the head of the linked list. So returning temp.next() is actually returning the list further to that head of the linked list.

Hope that helps.