AC Java solution without using stack


  • 0
    E

    The basic idea is the following 5 steps, the code is not concise but the idea is straightforward:

    1. Get the length of both list
    2. Pad 0s to the front of the shorter list
    3. Adding each digit and store the result backwards in the intermediate result
    4. walk through intermediate result and take care of carrying
    5. reverse the intermedia list to be result
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int len1 = getLen(l1);
            int len2 = getLen(l2);
            // padding 0s
            if (len1 >= len2) {
               for (int i = 0; i < len1 - len2; i++) {
                   ListNode node = new ListNode(0);
                   node.next = l2;
                   l2 = node;
               } 
            } else {
               for (int i = 0; i < len2 - len1; i++) {
                   ListNode node = new ListNode(0);
                   node.next = l1;
                   l1 = node;
               } 
            }
            // adding
            ListNode head = new ListNode(-1);
            while (l1 != null) {
                ListNode temp = new ListNode(l1.val + l2.val);
                temp.next = head.next;
                head.next = temp;
                l1 = l1.next;
                l2 = l2.next;
            }
            // taking care of overflow
            ListNode temp = head.next;
            ListNode prev = head;
            int val = 0;
            while (temp != null) {
                int old_val = temp.val;
                temp.val = (temp.val + val) % 10;
                val = (old_val + val) / 10;
                temp = temp.next;
                prev = prev.next;
            }
            if (val != 0) {
                prev.next = new ListNode(val);
            }
            // reverse
            return reverse(head.next);
            
        }
        private ListNode reverse(ListNode head) {
            ListNode prev = null;
            while (head != null) {
                ListNode next = head.next;
                head.next = prev;
                prev = head;
                head = next;
            }
            return prev;
        }
        private int getLen(ListNode node) {
            int len = 0;
            while (node != null) {
                len++;
                node = node.next;
            }
            return len;
        }
    }
    

Log in to reply
 

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