Fading Coder

One Final Commit for the Last Sprint

Home > Tech > Content

Summing Two Numbers Represented by Linked Lists

Tech 1

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...

Comprehensive Guide to SSTI Explained with Payload Bypass Techniques

Introduction Server-Side Template Injection (SSTI) is a vulnerability in web applications where user input is improper handled within the template engine and executed on the server. This exploit can r...

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...

Leave a Comment

Anonymous

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