Straightforward O(n) Java Solution Without Modifying Input Lists


  • 6
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            
            HashMap<Integer, Integer> hm1 = new HashMap<>(); //Store the 'index' and the value of List1
            HashMap<Integer, Integer> hm2 = new HashMap<>(); //Store the 'index' and the value of List2
            int i = 1, j = 1;
            
            while(l1 != null){
                hm1.put(i, l1.val);
                l1 = l1.next;
                i++;
            }
            while(l2 != null){
                hm2.put(j, l2.val);
                l2 = l2.next;
                j++;
            }
            
            int carry = 0;
            i--; j--;
            ListNode head = null;
            
          //Create new nodes to the front of a new LinkedList
            while(i > 0 || j > 0 || carry > 0){
    
                int a = i > 0 ? hm1.get(i) : 0;
                int b = j > 0 ? hm2.get(j) : 0;
                int res = (a + b + carry) % 10;
                
                ListNode newNode = new ListNode(res);
                newNode.next = head;
                head = newNode;
                
                carry = (a + b + carry) / 10;
                i--; j--;
            }
            return head;
        }
    }
    

  • 0
    N

    @ZachC
    If you initialize i = 0 and j = 0, then there wont be a need to decrement them both before the 3rd while loop, right ? We can avoid the 2 decrement statements.


  • 0

    @noob_coder Thanks for your advice. :)


  • 0
    A

    Nice work. Same advice with noob_coder.


  • 0
    K

    Use a stack instead of a HashMap will save you space and also will get rid of the decrement statements.

            Stack<Integer> s1 = new Stack<Integer>();
            Stack<Integer> s2 = new Stack<Integer>();
    
            while (l1 != null) {
              s1.push(l1.val);
              l1 = l1.next;
            }
            while (l2 != null) {
              s2.push(l2.val);
              l2 = l2.next;
            }
    
            int carry = 0;
            ListNode head = null;
    
            while(!s1.empty() || !s2.empty() || carry != 0) {
              if (!s1.empty()) {
                carry += s1.pop();
              }
              if (!s2.empty()) {
                carry += s2.pop();
              }
                ListNode node = new ListNode(carry % 10);
                node.next = head;
                head = node;
                carry /= 10;
            }
    
            return head;
    

Log in to reply
 

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