Fading Coder

One Final Commit for the Last Sprint

Home > Tech > Content

Summing Two Numbers Represented by Linked Lists

Tech May 3 13

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;
    }
}

Related Articles

Understanding Strong and Weak References in Java

Strong References Strong reference are the most prevalent type of object referencing in Java. When an object has a strong reference pointing to it, the garbage collector will not reclaim its memory. F...

Implement Image Upload Functionality for Django Integrated TinyMCE Editor

Django’s Admin panel is highly user-friendly, and pairing it with TinyMCE, an effective rich text editor, simplifies content management significantly. Combining the two is particular useful for bloggi...

SBUS Signal Analysis and Communication Implementation Using STM32 with Fus Remote Controller

Overview In a recent project, I utilized the SBUS protocol with the Fus remote controller to control a vehicle's basic operations, including movement, lights, and mode switching. This article is aimed...

Leave a Comment

Anonymous

◎Feel free to join the discussion and share your thoughts.