Java Program To Add Two Numbers Represented By Linked Lists- Set 1

0 0 3 minutes read

Given two numbers represented by two lists, write a function that returns the sum list. The sum list is a list representation of the addition of two input numbers.

Example:

Input: 
List1: 5->6->3 // represents number 563 
List2: 8->4->2 // represents number 842 
Output: 
Resultant list: 1->4->0->5 // represents number 1405 
Explanation: 563 + 842 = 1405

Input: 
List1: 7->5->9->4->6 // represents number 75946
List2: 8->4 // represents number 84
Output: 
Resultant list: 7->6->0->3->0// represents number 76030
Explanation: 75946+84=76030

Approach: Traverse both lists and One by one pick nodes of both lists and add the values. If the sum is more than 10 then make carry as 1 and reduce sum. If one list has more elements than the other then consider the remaining values of this list as 0.

The steps are:

Traverse the two linked lists from start to end
Add the two digits each from respective linked lists.
If one of the lists has reached the end then take 0 as its digit.
Continue it until both the end of the lists.
If the sum of two digits is greater than 9 then set carry as 1 and the current digit as sum % 10

Below is the implementation of this approach.

Java

// Java program to add two numbers 
// represented by linked list 
class LinkedList  
{ 
    static Node head1, head2; 
  
    static class Node  
    { 
        int data; 
        Node next; 
  
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
  
    /* Adds contents of two linked 
       lists and return the head node 
       of resultant list */
    Node addTwoLists(Node first,  
                     Node second) 
    { 
        // res is head node of the  
        // resultant list 
        Node res = null; 
        Node prev = null; 
        Node temp = null; 
        int carry = 0, sum; 
  
        // while both lists exist 
        while (first != null || 
               second != null)  
        { 
            // Calculate value of next digit  
            // in resultant list. The next  
            // digit is sum of following things 
            // (i)  Carry 
            // (ii) Next digit of first 
            // list (if there is a next digit) 
            // (ii) Next digit of second 
            // list (if there is a next digit) 
            sum = carry + (first != null ? first.data : 0) +  
                  (second != null ? second.data : 0); 
  
            // Update carry for next calculation 
            carry = (sum >= 10) ? 1 : 0; 
  
            // Update sum if it is greater  
            // than 10 
            sum = sum % 10; 
  
            // Create a new node with sum as data 
            temp = new Node(sum); 
  
            // if this is the first node then set 
            // it as head of the resultant list 
            if (res == null)  
            { 
                res = temp; 
            } 
  
            // If this is not the first 
            // node then connect it to the rest. 
            else 
            { 
                prev.next = temp; 
            } 
  
            // Set prev for next insertion 
            prev = temp; 
  
            // Move first and second pointers 
            // to next nodes 
            if (first != null)  
            { 
                first = first.next; 
            } 
            if (second != null)  
            { 
                second = second.next; 
            } 
        } 
  
        if (carry > 0)  
        { 
            temp.next = new Node(carry); 
        } 
  
        // return head of the resultant  
        // list 
        return res; 
    } 
  
    /* Utility function to print a  
       linked list */
    void printList(Node head) 
    { 
        while (head != null)  
        { 
            System.out.print(head.data +  
                             " "); 
            head = head.next; 
        } 
        System.out.println(""); 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        LinkedList list = new LinkedList(); 
  
        // Creating first list 
        list.head1 = new Node(7); 
        list.head1.next = new Node(5); 
        list.head1.next.next = new Node(9); 
        list.head1.next.next.next =  
        new Node(4); 
        list.head1.next.next.next.next =   
        new Node(6); 
        System.out.print("First List is "); 
        list.printList(head1); 
  
        // Creating second list 
        list.head2 = new Node(8); 
        list.head2.next = new Node(4); 
        System.out.print("Second List is "); 
        list.printList(head2); 
  
        // Add the two lists and see the result 
        Node rs = list.addTwoLists(head1, head2); 
        System.out.print("Resultant List is "); 
        list.printList(rs); 
    } 
} 
// This code is contributed by Mayank Jaiswal 

Output:

First List is 7 5 9 4 6 
Second List is 8 4 
Resultant list is 5 0 0 5 6

Complexity Analysis:

Time Complexity: O(m + n), where m and n are numbers of nodes in first and second lists respectively.
The lists need to be traversed only once.
Space Complexity: O(m + n).
A temporary linked list is needed to store the output number

Please refer complete article on Add two numbers represented by linked lists | Set 1 for more details!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!