Java O(n) with break condition


  • 0
    M

    If one of the list is end and the carry is 0, we don't need to scan the rest nodes.

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1==null) return l2;
            if(l2==null) return l1;
            ListNode head = new ListNode(0);
            ListNode p1 = l1, p2 = l2, h = head;
            int carry = 0, sum = 0;
            while(p1!=null && p2!=null){
                sum = p1.val + p2.val + carry;
                if(sum<10){
                    h.next = new ListNode(sum);
                    carry = 0;
                } else {
                    h.next = new ListNode(sum-10);
                    carry = 1;
                }
                p1 = p1.next;
                p2 = p2.next;
                h = h.next;
            }
            while(p1 != null){
                if(carry == 0){
                    h.next = p1;
                    break;
                }
                sum = p1.val + carry;
                if(sum<10){
                    h.next = new ListNode(sum);
                    carry = 0;
                } else {
                    h.next = new ListNode(sum-10);
                    carry = 1;
                }
                p1 = p1.next;
                h = h.next;
            }
            while(p2 != null){
                if(carry == 0){
                    h.next = p2;
                    break;
                }
                sum = p2.val + carry;
                if(sum<10){
                    h.next = new ListNode(sum);
                    carry = 0;
                } else {
                    h.next = new ListNode(sum-10);
                    carry = 1;
                }
                p2 = p2.next;
                h = h.next;
            }
            if(carry == 1){
                h.next = new ListNode(1);
            }
            return head.next;
        }
    }
    

Log in to reply
 

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