Burak Dede's Blog

Add Two Numbers Problem - Leetcode

Problem

This is my approach to the solution of add two numbers problem from Leetcode. https://leetcode.com/problems/add-two-numbers/description/

Cases

  • If two numbers are same length
  • One number is longer than other
  • How to return head of the result list (may be dummy head)?
  • What about extra carry over like adding 300 + 700 = 1000?
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

Solution #1

We can start looking for each element in linked lists and keep adding like we are adding two numbers digit by digit. Keep sum for the actual sum and remainder for the carry over. Sum would be sum % 10 and reminder would be sum / 10.

  • watch out for extra carry over like adding 700 + 300 = 1000, check remainder after loop
  • extra caution for non equal length numbers like 700 + 3 = 703, null checks in loop
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode result = dummyHead;

    int rem = 0;
    while(l1 != null || l2 != null) {
        int digit1 = (l1 != null) ? l1.val : 0;
        int digit2 = (l2 != null) ? l2.val : 0;
        int sum = digit1 + digit2 + rem;
        result.next = new ListNode(sum % 10);
        rem = sum / 10;
        l1 = (l1 != null) ? l1.next : l1;
        l2 = (l2 != null) ? l2.next : l2;
        result = result.next;
    }

    // we may have extra carry over
    if(rem != 0) {
        result.next = new ListNode(1);
    }

    return dummyHead.next;
}

Considering first number is N length and second number is M length with this algorithm time complexity is O(max(N, M)) and space complexity is O(max(N, M)).

I was able to come up only with one solution for this problem. For different length numbers you can end the loop and add remaining elements from non null list to the end of the result by carrying remainder but this would take more coding.

Submitted and seems like it passes test cases successfully.

[UPDATE] Leetcode solution is using extra two pointers for tracking each digits, this may be needed if want to use them again which in my case you lost heads.