Find the sum of two linked lists using Stack

Write a program to Sum of two linked list

Example:

Input: List1= 9->8->8->4->NULL, List2=5->2->8->NULL
Output: 1->0->4->1->2->NULL

Approach

Java

import java.util.Stack;

public class LinkedListSum {
    public static void main(String[] args) {
        // first linked list
        ListNode l1 = new ListNode(9);
        l1.next = new ListNode(8);
        l1.next.next = new ListNode(8);
        l1.next.next.next = new ListNode(4);

        // second linked list
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(8);
        //sum of both list
        ListNode sum = sumTwoList(l1, l2);
        // traversal the sum list
        linkedListTraversal(sum);
    }

    // method used for sum two linked list
    private static ListNode sumTwoList(ListNode l1, ListNode l2) {
        // base case
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        // create two stack
        Stack<ListNode> s1 = new Stack<ListNode>();
        Stack<ListNode> s2 = new Stack<ListNode>();
        // iterate till end of l1
        while (l1 != null) {
            // add value in stack
            s1.add(l1);
            l1 = l1.next;

        }
        // iterate till end of l2
        while (l2 != null) {
            // add value in stack
            s2.add(l2);
            l2 = l2.next;

        }
        int carry = 0;
        ListNode root = null;
        ListNode tmp = null;
        // iterate till both not empty
        while (!s1.isEmpty() && !s2.isEmpty()) {
            ListNode n1 = s1.pop();
            ListNode n2 = s2.pop();
            int sum = n1.val + n2.val + carry;
            n1.val = sum % 10;
            if (root == null) {
                root = n1;
                tmp = n1;
            } else {
                tmp.next = n1;
                tmp = n1;
            }
            carry = sum / 10;
        }
        // if s1 not empty
        while (!s1.isEmpty()) {
            ListNode n1 = s1.pop();
            int sum = n1.val + carry;
            n1.val = sum % 10;
            tmp.next = n1;
            tmp = n1;
            carry = sum / 10;
        }
        // if s2 not empty
        while (!s2.isEmpty()) {
            ListNode n2 = s2.pop();
            int sum = n2.val + carry;
            n2.val = sum % 10;
            tmp.next = n2;
            tmp = n2;
            carry = sum / 10;
        }
        // carry is still
        if (carry > 0) {
            tmp.next = new ListNode(carry);
            tmp = tmp.next;
        }
        tmp.next = null;
        //reverse the list
        ListNode reverse=reverseList(root);
        return reverse;
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode c = head;
        ListNode prev = null;
        while (c != null) {
            ListNode n = c.next;
            c.next = prev;
            prev = c;
            c = n;
        }
        return prev;
    }

    private static void linkedListTraversal(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
}


class ListNode implements Comparable<ListNode> {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public int compareTo(ListNode o) {
        if (this.val == o.val)
            return 0;
        else if (this.val > o.val)
            return 1;
        else
            return -1;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//Struture of  node
struct Node
{ 
   int data;
   Node *next;
   Node(int data)
    {
        this->data=data;
        this->next=NULL;
    }
};
//function to traverse a linked 
//list
void linkedListTraversal(Node *head)
{
    Node *temp=head;
    //iterate till we reach end of the linked 
    //list
    while(temp!=NULL)
     {
         //print the current
         //node data
         cout<<temp->data<<" ";
         //move to next node
         temp=temp->next;
     }
}

//Function to reverse the linklist
Node *reverseList(Node *head)
{
    if(head==NULL)
       return head;
    Node *curr=head,*prev=NULL,*temp=head;
    while(curr!=NULL)
      {
         temp=curr->next;
         curr->next=prev;
         prev=curr;
         curr=temp;
      }
    return prev;
}
//function used for sum two linked list
Node* sumTwoList(Node *l1, Node *l2) 
{
        // base case
        if (l1 == NULL)
            return l2;
        if (l2 == NULL)
            return l1;
        // create two stack
        stack<Node*> s1;
        stack<Node*> s2;
        // iterate till end of l1
        while (l1 != NULL) {
            // add value in stack
            s1.push(l1);
            l1 = l1->next;

        }
        // iterate till end of l2
        while (l2 != NULL) {
            // add value in stack
            s2.push(l2);
            l2 = l2->next;

        }
        int carry = 0;
        Node *root =NULL;
        Node *tmp = NULL;
        // iterate till both not empty
        while (!s1.empty() && !s2.empty())
         {
            Node *n1 = s1.top();
            s1.pop();
            Node *n2 = s2.top();
            s2.pop();
            int sum = n1->data + n2->data + carry;
            n1->data = sum % 10;
            if (root ==NULL) {
                root = n1;
                tmp = n1;
            } else {
                tmp->next = n1;
                tmp = n1;
            }
            carry = sum / 10;
        }
        // if s1 not empty
        while (!s1.empty()) {
            Node *n1 = s1.top();
            s1.pop();
            int sum = n1->data + carry;
            n1->data = sum % 10;
            tmp->next = n1;
            tmp = n1;
            carry = sum / 10;
        }
        // if s2 not empty
        while (!s2.empty()) {
            Node *n2 = s2.top();
            s2.pop();
            int sum = n2->data + carry;
            n2->data = sum % 10;
            tmp->next = n2;
            tmp = n2;
            carry = sum / 10;
        }
        // carry is still
        if (carry > 0) {
            tmp->next = new Node(carry);
            tmp = tmp->next;
        }
        tmp->next = NULL;
        //reverse the list
        Node *reverse=reverseList(root);
        return reverse;
}
int main()
{
    // first linked list
    Node *l1 = new Node(9);
    l1->next = new Node(8);
    l1->next->next = new Node(8);
    l1->next->next->next = new Node(4);

    // second linked list
    Node *l2 = new Node(5);
    l2->next = new Node(2);
    l2->next->next = new Node(8);
    //sum of both list
    Node *sum = sumTwoList(l1, l2);
    // traversal the sum list
    linkedListTraversal(sum);
}