Add Two Numbers as Lists Editorial

Practice Problem Link: Add Two Numbers as Lists

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two natural numbers, a and b, represented as reversed linked lists, compute their sum c as another reversed linked list.

Approach

Traverse both the list simultaneously and add the corresponding value of nodes in a new list. If the sum exceeds 9 then set carry as 1 and sum as sum % 10. If one list has more elements than the other list, consider the list's remaining values separately.

Analysis

• Time Complexity: O(n), (n>m)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

ListNode* addTwoNumbers(ListNode* firstList, ListNode* secondList) {
	ListNode *head = NULL, *prev = NULL;
	int carry = 0;
	while (firstList != NULL || secondList != NULL) {
		int val1 = firstList != NULL ? firstList->data : 0;
		int val2 = secondList != NULL ? secondList->data : 0;
		int sum = val1 + val2 + carry;
		carry = sum / 10;
		int val = sum % 10;
		ListNode* curr = new ListNode(val);
		if (head == NULL) {
			head = curr;
		}
		if (prev != NULL) {
			prev->next = curr;
		}
		prev = curr;
		firstList = firstList != NULL ? firstList->next : NULL;
		secondList = secondList != NULL ? secondList->next : NULL;
	}
	if(carry > 0) {
		ListNode* extraNode = new ListNode(carry);
		prev->next = extraNode;
	}
	return head;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode addTwoNumbers(ListNode firstList, ListNode secondList) {
		ListNode head = null, prev = null;
		int carry = 0;
		while (firstList != null || secondList != null) {
			int val1 = firstList != null ? firstList.data : 0;
			int val2 = secondList != null ? secondList.data : 0;
			int sum = val1 + val2 + carry;
			carry = sum / 10;
			int val = sum % 10;
			ListNode curr = new ListNode(val);
			if (head == null) {
				head = curr;
			}
			if (prev != null) {
				prev.next = curr;
			}
			prev = curr;
			firstList = firstList != null ? firstList.next : null;
			secondList = secondList != null ? secondList.next : null;
		}
		if(carry > 0) {
			ListNode extraNode = new ListNode(carry);
			prev.next = extraNode;
		}
		return head;
	}
}