O(n) Just Plain Traversal (No Extraspace / No modification to input lists) Beats 64%


  • 0
    M

    Idea : Get the lengths of both the lists.O(n). create a result list with the sum of digits at respective positions(these additions might contains >10 (ignore carry for now)) O(n). reverse the result list O(n) without extra space. Next compute the carry and modify the value in the node. For the final result reverse the result list again. O(n).

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	int l1len = 0, l2len = 0, l1l, l2l;
    	ListNode temp;
    	temp = l1;
    	while(temp!= null){
    		temp = temp.next;
    		l1len++;
    	}
    	temp = l2;
    	while(temp!= null){
    		temp = temp.next;
    		l2len++;
    	}
    
    	if(l1len==0) return l2;
    	if(l2len==0) return l1;
    	if(l1len < l2len) {
    		temp  = l1 ;
    		l1 = l2;
    		l2 = temp;
    		l2l = l1len;
    		l1l = l2len;
    	}else{
    		l1l = l1len;
    		l2l = l2len;
    	}
    	ListNode head = null, prev = null;
    	while(l1l != l2l) {
    		temp = new ListNode(l1.val);
    		if(head == null) { head = temp; prev = temp; } 
    		else{
    			prev.next = temp;
    			prev = temp;
    		}
    		l1 = l1.next;
    		l1l--;
    	}
    
    	while(l1l >0 && l2l >0){
    		temp = new ListNode(l1.val + l2.val);
    		if(head == null) { head = temp; prev = temp; } 
    		else{
    			prev.next = temp;
    			prev = temp;
    		}
    		l1 = l1.next; l2 = l2.next;
    		l1l--; l2l--;
    	}
    
    	head = reverse(head);
    	compute(head);
    	head = reverse(head);
    	return head;
    }
    
    public ListNode reverse(ListNode node){
    	ListNode prev = null, head = node, next, temp = node;
    	while(temp != null){
    		next = temp.next;
    		temp.next = prev;
    		prev = temp;
    		temp = next;
    	}
    	return prev;
    }
    
    public void compute(ListNode head){
    	int carry = 0;
    	ListNode temp = head, prev = head;
    	while(temp != null){
    		temp.val = temp.val + carry;
    		carry = temp.val / 10; 
    		temp.val = temp.val % 10;
    		prev = temp;
    		temp =  temp.next;
    	}
    	if(carry > 0) prev.next = new ListNode(carry);
    }
    

Log in to reply
 

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