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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!