Summing Two Numbers Represented by Linked Lists
The problem involves adding two non-negative integers represented by linked lists where digits are stored in reverse order. Each node contains a single digit. The result should also be returned as a linked list with digits in reverse order. It is assumed that the input lists do not contain leading zeros, except for the number zero itself.
Example Input:
List A: 2 -> 4 -> 3
List B: 5 -> 6 -> 4
Example Output:
7 -> 0 -> 8
Explanation: The input lists represent 342 and 465 respectively. The sum is 807, which corresponds to the output list 7 -> 0 -> 8.
To solve this, we traverse both lists simultaneously from the head. Since the least significant digit is at the head, we can perform elementary addition digit by digit. We maintain a carry variable initialized to zero. For each iteration, we calculate the sum of the current digits from both lists and the carry. The new digit for the result list is the sum modulo 10, and the new carry is the sum divided by 10. The iteration continues until both lists are exhausted and there is no remaining carry.
The following C# implementation demonstrates this logic:
public ListNode SumTwoLinkedLists(ListNode listA, ListNode listB)
{
ListNode dummyHead = new ListNode(0);
ListNode current = dummyHead;
int remainder = 0;
while (listA != null || listB != null || remainder > 0)
{
int x = (listA != null) ? listA.val : 0;
int y = (listB != null) ? listB.val : 0;
int totalSum = x + y + remainder;
remainder = totalSum / 10;
int currentDigit = totalSum % 10;
current.next = new ListNode(currentDigit);
current = current.next;
if (listA != null) listA = listA.next;
if (listB != null) listB = listB.next;
}
return dummyHead.next;
}
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}