My favorite Java recursive solution : a clean and fancy way


  • 0
    1. put the longer list in front.

    2. Take one or two nodes out of lists and make the rest of them a subproblem. The recursive function will generate the sum of current nodes and update its parent node as the carry.

    
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int size1 = getLength(l1);
            int size2 = getLength(l2);
            ListNode head = new ListNode(0);
            // Make sure l1.length >= l2.length
            head.next = size1 < size2 ? helper(l2, l1, head, size2 - size1) : helper(l1, l2, head, size1 - size2);
            
            return head.val == 1 ? head : head.next;
        }
        
        public int getLength(ListNode l) {
            int count = 0;
            while (l != null) {
                l = l.next;
                count++;
            }
            return count;
        }
        
        private ListNode helper(ListNode l1, ListNode l2, ListNode head, int offset) {
            if (l1 == null) return null;
            
            ListNode cur = new ListNode (0);
            int sum = 0;
            if (offset > 0) {
                cur.next = helper(l1.next, l2, cur, offset - 1);
                sum = cur.val + l1.val;
            } else {
                cur.next = helper(l1.next, l2.next, cur, offset);
                sum = cur.val + l1.val + l2.val;
            }
            
            cur.val = sum % 10;
            head.val = sum / 10;
            
            return cur;
        }
        
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.