JAVA recursive approach with the thought of adding 2 lists with the same length


  • 0
    B

    helper() is recursively adding 2 lists with the same length. the returned list contains the carryover value at the head which is either 0 or 1.

    if l1 and l2 is not the same length then add nodes with 0 value to the head of either one to make them equal.

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            
            ListNode node1 = l1;
            ListNode node2 = l2;
            while(node1 != null && node2 != null){
                node1 = node1.next;
                node2 = node2.next;
            }
            
            if (node1 != null)
                
                while (node1 != null){ //adding leading 0
                    ListNode temp = new ListNode(0);
                    temp.next = l2;
                    l2 = temp;
                    node1 = node1.next;
                }
                
            else
            
                while (node2 != null){
                    ListNode temp = new ListNode(0);
                    temp.next = l1;
                    l1 = temp;
                    node2 = node2.next;
                }
            
            //now l1 length == l2.length
                
            ListNode ret = helper(l1, l2);
            if (ret.val == 0)
                ret = ret.next;
                
            return ret;    
            
        }
        
        private ListNode helper(ListNode node1, ListNode node2){
            
            if (node1 == null)
                return null;
    
            ListNode node = helper(node1.next, node2.next);
    
            int val = node1.val + node2.val;
            
            if (node != null)
                val += node.val;
            
            ListNode head = new ListNode(val/10);
            
            ListNode sum = new ListNode(val%10);
            
            if (node != null)
                sum.next = node.next;
            
            head.next = sum;
            
            return head;
        }
        
    }
    

Log in to reply
 

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