O(n) Java Solution without using stack or recursion. Space O(1)


  • 0
    C
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode cur1 = l1, cur2 = l2;
            int size1 = 0, size2 = 0;
            while (cur1 != null){
                size1++;
                cur1 = cur1.next;
            }
            while (cur2 != null){
                size2++;
                cur2 = cur2.next;
            }
            
            if (size1 < size2){
                ListNode temp = l1;
                l1 = l2;
                l2 = temp;
                int size = size1;
                size1 = size2;
                size2 = size;
            }
            ListNode sumHead = new ListNode(0);
            ListNode sumCur = sumHead, sumPre = sumHead;
            cur1 = l1;
            cur2 = l2;
            for (int i = size1 - size2; i > 0; i--){
                ListNode sumNode = new ListNode(cur1.val);
                sumCur.next = sumNode;
                if (sumNode.val < 9){
                    sumPre = sumNode;
                }
                sumCur = sumNode;
                cur1 = cur1.next;
            }
            
            while (cur1 != null){
                ListNode sumNode = new ListNode(cur1.val + cur2.val);
                sumCur.next = sumNode;
                if (sumNode.val >= 10){
                    sumNode.val -= 10;
                    sumPre.val += 1;
                    while (sumPre != sumCur){
                        sumPre = sumPre.next;
                        sumPre.val = 0;
                    }
                    sumPre = sumNode;
                } else if (sumNode.val < 9){
                    sumPre = sumNode;
                }
                sumCur = sumNode;
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return sumHead.val == 0 ? sumHead.next : sumHead;
            
        }
    }
    

Log in to reply
 

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