O(n) Java solution without list modification/Stack (reversed list wrapper)


  • 0
    D
    public class Solution {
        private static class Node {
            ListNode node;
            Node prev;
            Node(ListNode n, Node p) {
                node = n;
                prev = p;
            }
        }
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Node t1 = null;
            Node t2 = null;
            
            while (l1 != null) {
                t1 = new Node(l1, t1);
                l1 = l1.next;
            }
            while (l2 != null) {
                t2 = new Node(l2, t2);
                l2 = l2.next;
            }
    
            ListNode res = null;
            int sum = 0;
            while (t1 != null || t2 != null || sum > 0) {
                if (t1 != null) {
                    sum += t1.node.val;
                    t1 = t1.prev;
                }
                if (t2 != null) {
                    sum += t2.node.val;
                    t2 = t2.prev;
                }
    
                ListNode node = new ListNode(sum % 10);
                node.next = res;
                res = node;
    
                sum /= 10;
            }
            return res; 
        }
    }
    

Log in to reply
 

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