addtwonumbers Leetcode question

[muregii]

https://github.com/muregii/codeKenya/blob/main/codeK(main)/Leetcode/0002-add-two-numbers/README.md

class Solution { public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode tempHead = new ListNode(0);
    ListNode list1 = l1, list2 = l2, current = tempHead;
    int numberCarried = 0;

    while(list1 != null || list2 != null){
        int x, y;
        if(list1 != null){
            x = list1.val;
        }
        else{
            x = 0;
        }

        if(list2 != null){
            y = list2.val;
        }
        else{
            y = 0;
        }

        int sum = x + y + numberCarried;
        numberCarried = sum/10;
        current.next = new ListNode(sum % 10);
        current = current.next;

        if(list1 != null) list1 = list1.next;
        if(list2 != null) list2 = list2.next;

    }

    if(numberCarried > 0){
        current.next = new ListNode(numberCarried);
    }

    return tempHead.next; 
}

}

Struggling to understand this code. Someone break it down. @muregii

[Patrick-Kariuki]

I tried following the code, but I think I have a simpler to follow solution. Let's break down the problem:

What we know: input: 2 singly linked lists representing two non-negative integers output: new linked list with the sum of the inputs the input is in reverse order, output should also be in reverse order 0 <= Node.val <= 9 input lists have at least one node but may not be of the same length guaranteed that the list represents a number that does not have leading zeros

We can match this problem with a temporary head technique. We are creating and returning a new linked list, so we need a way to keep track of the linked list we are creating.

With that in mind, we can develop the following pseudocode:

1. create a temp head
2. create a carry value
3. while we have values to add in both LL: a. add the values and carry, and create a new node appended to answer i. get the sum ii. append node iii. retain the carry b. advance pointers in both LLs
4. if l1 != null, append to answer
5. if l2 != null, append to answer
6. if carry > 0, append to answer
7. return temp.next

The code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(0);
        ListNode curr = temp;
        int carry = 0;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + carry;
            curr.next = new ListNode(sum % 10);
            carry = sum / 10;
            curr = curr.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        // edge case: uneven lists
        while (l1 != null) {
            int sum = l1.val + carry;
            curr.next = new ListNode(sum % 10);
            carry = sum / 10;
            curr = curr.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            int sum = l2.val + carry;
            curr.next = new ListNode(sum % 10);
            carry = sum / 10;
            curr = curr.next;
            l2 = l2.next;
        }
        // edge case: still have a carry
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return temp.next;
    }
}

Review of the Solution: Time complexity: O(n + m) because we have to traverse through all elements in both linked lists. Space complexity: O(n) or O(m) because the maximum number of digits we need to store is the number of digits in the longer list, plus one more of the temp head.

I hope that helps!