LeetCode (Algorithms#2) ‒Add Two Numbers

Problem

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution

The solution requires linear time and space, and is pretty straightforward. We perform simple addition as we were taught in elementary mathematics, starting with the smaller digits and carrying a 1 if necessary. The only trick is to do it in one loop which is easy because the digits are provided in reverse order. What if they weren't? Some backwards recursion could do the trick.

Time complexity: O(n)
Space complexity: O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode res = new ListNode(0); ListNode curs = res; ListNode cur1 = l1; ListNode cur2 = l2; int sum; boolean carry = false; while (true) { sum = (cur1 == null ? 0 : cur1.val) + (cur2 == null ? 0 : cur2.val) + (carry ? 1 : 0); carry = sum >= 10; curs.val = sum % 10; if ((cur1 == null || cur1.next == null) && (cur2 == null || cur2.next == null)) { if (carry) { curs.next = new ListNode(1); } break; } else { curs.next = new ListNode(0); curs = curs.next; cur1 = (cur1 == null ? null : cur1.next); cur2 = (cur2 == null ? null : cur2.next); } } return res; }