# Sum of Two Linked Lists Representing Numbers – IQCode

### Adding Two Numbers: Coding Solutions and FAQs

Here we present solutions in C++, Java, and Python to the problem of adding two numbers.

Problem Statement: Given two non-empty linked lists representing two non-negative integers, add the two numbers and return them as a linked list.

Approach: We will iterate through the linked lists, adding the values of each node together, and creating a new node with the sum of the values. If the sum is greater than 9, we carry the 1 to the next node. If one list is shorter than the other, we substitute 0 for the missing value to continue the summation.

#### C++ Code:

``` struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };```

``` ```

```class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* res = new ListNode(0); ListNode* curr = res; int carry = 0; while (l1 || l2 || carry) { int v1 = l1 ? l1->val : 0; int v2 = l2 ? l2->val : 0; int sum = v1 + v2 + carry; carry = sum / 10; curr->next = new ListNode(sum % 10); curr = curr->next; l1 = l1 ? l1->next : l1; l2 = l2 ? l2->next : l2; } return res->next; } }; ```

#### Java Code:

``` public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode res = new ListNode(0); ListNode curr = res; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int v1 = l1 != null ? l1.val : 0; int v2 = l2 != null ? l2.val : 0; int sum = v1 + v2 + carry; carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; l1 = l1 != null ? l1.next : l1; l2 = l2 != null ? l2.next : l2; } return res.next; } } ```

#### Python Code:

``` class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: res = ListNode(0) curr = res carry = 0 while l1 or l2 or carry: v1 = l1.val if l1 else 0 v2 = l2.val if l2 else 0 summ = v1 + v2 + carry carry = summ // 10 curr.next = ListNode(summ % 10) curr = curr.next l1 = l1.next if l1 else l1 l2 = l2.next if l2 else l2 return res.next ```

#### FAQs:

• What is the time complexity of this algorithm? The time complexity is O(max(m,n)), where m and n are the lengths of the linked lists representing the two numbers.
• What is the space complexity of this algorithm? The space complexity is also O(max(m,n)), due to the creation of a new linked list to store the result.
• What is a linked list? A linked list is a data structure consisting of a collection of nodes, each containing a value and a reference (or pointer) to the next node in the sequence.

Given two numbers represented as LinkedList, this program finds the sum of two numbers represented as LinkedList.

#### Sample Test Cases:

TestCase 1:

``` //First input LinkedList ListNode firstList = new ListNode(7); firstList.next = new ListNode(5); firstList.next.next = new ListNode(9); firstList.next.next.next = new ListNode(4); firstList.next.next.next.next = new ListNode(6);```

``` //Second input LinkedList ListNode secondList = new ListNode(8); secondList.next = new ListNode(4); ```

```//Expected Output LinkedList ListNode Result = new ListNode(5); Result.next = new ListNode(0); Result.next.next = new ListNode(0); Result.next.next.next = new ListNode(5); Result.next.next.next.next = new ListNode(6); ```

TestCase 2:

``` //First input LinkedList ListNode firstList = new ListNode(0);```

``` //Second input LinkedList ListNode secondList = new ListNode(0); ```

```//Expected Output LinkedList ListNode Result = new ListNode(0); ```

Explanation:

In the first test case, firstList = 75946 and secondList = 84. Sum of these numbers results in 50056.

In the second test case, both the lists represent number 0, hence the output is also number 0.

The following algorithm is used to perform addition on two linked lists:

1. Traverse both linked lists and append zeros to the shorter list until both lists have an equal number of digits.
2. Begin a recursive function at the start nodes of both lists.
3. Recursively move ahead on both lists until the end is reached.
4. Create new nodes during recursion to store the sum of digits, returning the carry to the next node for the sum operation.

### Adding Two Numbers as Lists: Solution

``` /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* A, ListNode* B) {```

``` ListNode* dummy = new ListNode(0); ListNode* current = dummy; int carry = 0; ```

``` while(A || B || carry){ int sum = 0; if(A){ sum += A->val; A = A->next; } if(B){ sum += B->val; B = B->next; } sum += carry; carry = sum / 10; current->next = new ListNode(sum % 10); current = current->next; } return dummy->next; } }; ```

This solution is for the problem “Add Two Numbers as Lists” and demonstrates how to add two numbers represented as linked lists. The solution iterates over each node in both linked lists and adds their values, accounting for any carried-over digits. The solution is optimized and has clear, concise code with comments.

### C++ Code: Summing Two Linked Lists

``` Node* addLinkedLists(Node* head1, Node* head2) { Node* res = NULL; Node* prev = NULL; Node* temp; int carry = 0; int sum = 0;```

``` while(head1 != NULL || head2 != NULL) { sum = carry + (head1 ? head1->data : 0) + (head2 ? head2->data : 0); carry = (sum >= 10) ? 1 : 0; sum = sum % 10; temp = newNode(sum); if(res == NULL) { res = temp; } else { prev->next = temp; } prev = temp; if(head1) { head1 = head1->next; } if(head2) { head2 = head2->next; } } if(carry > 0) { temp->next = newNode(carry); } return res; } Node* reverseList(Node* head) { if(head == NULL || head->next == NULL) { return head; } Node* rest = reverseList(head->next); head->next->next = head; head->next = NULL; return rest; } Node* sumLinkedLists(Node* list1, Node* list2) { list1 = reverseList(list1); list2 = reverseList(list2); ```

``` Node* added = addLinkedLists(list1, list2); return reverseList(added); } ```

``` public static Node addLists(Node first, Node second) {```

``` // create new nodes with value 0 before the first node of each list Node start1 = new Node(0); start1.next = first; Node start2 = new Node(0); start2.next = second; // add preceding zeros if one list is longer than the other addPrecedingZeros(start1, start2); // set up result node and perform addition until end of both nodes Node result = new Node(0); if (sumNodes(start1.next, start2.next, result) == 1) { Node dummy = new Node(1); dummy.next = result.next; result.next = dummy; } return result.next; } // perform two-node addition recursively and return carry public static int sumNodes(Node first, Node second, Node result) { if (first == null) { return 0; } int sum = 0; sum += first.data; sum += second.data; sum += sumNodes(first.next, second.next, result); Node dummy = new Node(sum % 10); dummy.next = result.next; result.next = dummy; return sum / 10; } // add preceding zeros to the shorter list public static void addPrecedingZeros(Node start1, Node start2) { Node next1 = start1.next; Node next2 = start2.next; while (next1 != null && next2 != null) { next1 = next1.next; next2 = next2.next; } if (next1 == null) { while (next2 != null) { Node dummy = new Node(0); dummy.next = start1.next; start1.next = dummy; next2 = next2.next; } } else if (next2 == null) { while (next1 != null) { Node dummy = new Node(0); dummy.next = start2.next; start2.next = dummy; next1 = next1.next; } } } public static Node addTwoLists(Node a, Node b) { return solve(a, b); } ```

```public static Node solve(Node first, Node second) { return addLists(first, second); } ```

This code adds two linked lists node-by-node, carrying over any sum greater than 9 to the next calculation. It ensures that both lists are of equal length by adding preceding zeros to the beginning of the shorter list. The final result is returned as a new linked list. Test cases and exceptions should be added to this code as necessary.

``` class Node: def __init__(self, data): self.data = data self.next = None```

``` ```

```def addLinkedLists(first, second): # Initialize variables to keep track of linked lists given as input, # results of addition, the "carry" digit, and the position in the list. prev, temp = None, None carry = 0 while first is not None or second is not None: # Handle cases where one list could be shorter than the other. if first is None: firstData = 0 else: firstData = first.data if second is None: secondData = 0 else: secondData = second.data Sum = carry + firstData + secondData carry = 1 if Sum >= 10 else 0 Sum %= 10 temp = Node(Sum) # Store addition results in a temporary linked list. if prev is None: head = temp else: prev.next = temp prev = temp # Position to next node in each linked list. if first is not None: first = first.next if second is not None: second = second.next # Add final carry if there is one. if carry > 0: temp.next = Node(carry) # Return head node of result linked list. return head ```

The given code performs the addition of two linked lists in linear time and space complexity. The updated function is optimized and assumes the input are valid linked lists

### FAQs

Q. Why are zeros added to the end of the shorter linked list?

A. Zeros are added to the end of the linked list to aid implementation of the problem logic. This is equivalent to adding zeros before a number and does not change the value of the list.

Q. How is the carry calculated for the addition of digits?

A. The carry is calculated for the sum of digits using the following rule: “If the sum of digits exceeds 10, the carry is 1, else it is 0.”

``` function addLinkedLists(l1, l2) { //logic for adding linked lists here } ```

``` //Detect Loop in Linked List```

``` //Reverse a Linked List //Delete Node in a Linked List //Intersection of Two Linked Lists //Linked List Interview Questions //Linked List MCQ //Application of Linked List ```

```//Types of Linked List ```