Java O(m+n) time and space w/o reversing any of the list.


  • 0
    S

    Idea behind it is very simple . Iterate thru given linked list and store them in separate stacks. Now keep popping each element and maintaining the total sum + carry(if any).

    Create a node with (sum%10) value and keep adding on the head . In that case you don't have to store or revere the output array.

    But I still feel reverse solution is better than this.

        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Stack<Integer> l1Stack = new Stack<>();
            Stack<Integer> l2Stack = new Stack<>();
    
            while(l1 != null){
                l1Stack.push(l1.val);
                l1 = l1.next;
            }
            while(l2 != null){
                l2Stack.push(l2.val);
                l2 = l2.next;
            }
            ListNode l3 = null;
            int carry = 0;
            while(!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry > 0){
                int sum = (l1Stack.isEmpty() ? 0 : l1Stack.pop()) + (l2Stack.isEmpty()? 0 : l2Stack.pop()) + carry;
                carry = sum / 10;
                ListNode head = new ListNode(sum%10);
                if(l3 == null) l3 = head;
                else {
                    head.next = l3;
                    l3 = head;
                }
            }
    
            return l3;
        }
    

Log in to reply
 

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