O(2N) Length Diff Recursion Solution


  • 0
    X
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	//999
    	//  1
    	int len1 = 0;
    	ListNode runner = l1;
    	while (runner != null) {
    		len1++;
    		runner = runner.next;
    	}
    
    	int len2 = 0;
    	runner = l2;
    	while (runner != null) {
    		len2++;
    		runner = runner.next;
    	}
    
    	if (len1 == 0 || len2 == 0) {
    		return len1 == 0 ? l2 : l1;
    	}
    
    	int[] carrier = {0};
    	ListNode longer = len1 > len2 ? l1 : l2;
    	ListNode shorter = l1 == longer? l2: l1;
    	ListNode subList = helper (longer, Math.max(len1, len2), shorter, Math.min(len1, len2), carrier);
    	ListNode dummy = new ListNode(-1);
    	if (carrier[0] == 1) {
    		dummy.next = new ListNode(1);
    		dummy.next.next = subList;
    	} else {
    		dummy.next = subList;
    	}
    	return dummy.next;
    
    }
    
     private ListNode helper (ListNode l1, int len1, ListNode l2, int len2, int[] carrier) {
    	ListNode curNode = null;
    	
    	if (len1 == len2) {
    		//stopping
    		if (len1 == 0) {
    			return null;
    		}
    
    		int[] currentCarrier = {0};
    		ListNode subList = helper (l1.next, len1 - 1,  l2.next, len2 - 1, currentCarrier);
    		int tempSum = l1.val + l2.val + currentCarrier[0];
    		curNode = new ListNode (tempSum % 10);
    		carrier[0] = tempSum / 10;
    		curNode.next = subList;
    
    		
    	}
    	
    	if (len1 > len2) {
    		int[] currentCarrier = {0};
    		ListNode subList = helper (l1.next, len1 - 1,  l2, len2, currentCarrier);
    		int tempSum = l1.val + currentCarrier[0];
    		curNode = new ListNode (tempSum % 10);
    		carrier[0] = tempSum / 10;
    		curNode.next = subList;
    	}
    	
    	return curNode;
    }

Log in to reply
 

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