My accepted Java solution


  • 60
    D

    Two things to make the code simple:

    1. Whenever one of the two ListNode is null, replace it with 0.
    2. Keep the while loop going when at least one of the three conditions is met.

    Let me know if there is something wrong. Thanks.

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode prev = new ListNode(0);
            ListNode head = prev;
            int carry = 0;
            while (l1 != null || l2 != null || carry != 0) {
                ListNode cur = new ListNode(0);
                int sum = ((l2 == null) ? 0 : l2.val) + ((l1 == null) ? 0 : l1.val) + carry;
                cur.val = sum % 10;
                carry = sum / 10;
                prev.next = cur;
                prev = cur;
                
                l1 = (l1 == null) ? l1 : l1.next;
                l2 = (l2 == null) ? l2 : l2.next;
            }
            return head.next;
        }
    }

  • 0
    C

    I'm confused with what is happening when:

            prev.next = cur;
            prev = cur;
    

    Can you elaborate??

    If the input is: 3->1-> 2 and 1

    According to your code, wouldn't the output be (incorrectly): 4->1->2

    Instead of the result (correct): 3->1->3


  • 4
    D

    This problem mentions that the digits of the number are stored in reverse order. So input 3 -> 1 -> 2 would represent 213 instead of 312, which plus 1, will give a result of 214 to be stored as 4 -> 1 -> 2.

    prev.next = cur;
    prev = cur;

    For these two lines of code, we need to keep track of the previous node, meaning that the last node of the linked list we have created, so that we have a way to append the new node to the linked list. So after we are done with a node which is cur, we append it after prev by doing prev.next = cur, and then we assign cur to be the previous node by prev = cur.


  • 0
    C

    Ohh makes sense, thanks.

    What happens in the final iteration to prev.next (which from the beginning would be prev.next.next.next in the example I provided)? Wouldn't we end up with 4->1->2->2?


  • 1
    D

    Let's say 3 -> 1 -> 2 is l1, and 1 is l2. At the final iteration, l1 will be at the last node which is 2, l2 will be null. We create a new node with value (2 + 0) = 2. And then at the next step l1 and l2 will be both null and the while loop will terminate. There won't be any duplication.


  • 0
    C

    What happens to prev.next in the final iteration, i.e. why is it not added to the list?


  • 3
    S

    Hi, your code is very nice in combining everything into one loop. I just have a suggestion that you could make

    ListNode cur = new ListNode(0);
    

    to be

    ListNode cur = l1!=null?l1:(l2!=null?l2:(new ListNode(0)));
    

    And that will save your O(n) space to O(1).


  • 2
    I

    The best part I liked about your answer was returning " head.next " !!!


  • 0
    Z

    @siyang3 Good catch :)
    Guess this depends on the requirement. Your code is moidfiying input list, right ?


  • 0
    S

    I like your code, it's very clean and simple. But how about if list 1 is very short and list 2 is very long, it is wasting time to keep checking the rest of the l2 when l1.next == null.


  • 0
    4

    Getting TLE for :

    [9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
    [1]


  • 0
    W

    Hello,
    Your code works well except for one problem. When I run it in Eclipse, it only return the first digit of the result since you return head.next at last. How did you manage to return the whole linked list according to return the whole linked list using "return head.next"
    Thanks so much for your help!


  • 0
    Y

    Thank you very much ! At the beginning, I can't understand the question. After I read your code I got it.


  • 0
    M

    Same code in a easy to read form.

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            
            if(l1 == null || l2 == null)
                return null;
            
            int carry = 0;
            
            ListNode n1 = l1;
            ListNode n2 = l2;
            
            ListNode newHead = new ListNode(0);
            ListNode l3 = newHead;
            
            while(n1 != null || n2 != null){
                int newVal = 0;
                if(n1 != null){
                   newVal += n1.val;
                   n1 = n1.next;
                }
                if(n2 != null){
                   newVal += n2.val;
                   n2 = n2.next;
                }
                
                newVal += carry;
                carry = newVal / 10;
                newVal = newVal%10;
                
                l3.next = new ListNode(newVal);
                l3 = l3.next;
            }
            
            if(carry == 1){
                l3.next = new ListNode(1);
            }
            
            return newHead.next;
            
        }
    }
    
    

  • 0
    S

    Please can someone explain me why do we return head.next?


  • 1
    M

    @sharma.karan9341
    The line ListNode prev = new ListNode(0); adds a dummy node for your result list to start. Since head points to this node and we don't want this node but the nodes following it the function returns head.next


  • 0
    R

    '''l1 = (l1 == null) ? l1 : l1.next;
    l2 = (l2 == null) ? l2 : l2.next;'''
    What are these lines actually meant for?


  • 0
    S

    @siyang3 why can space change from o(n) to o(1), i can't quiet understand please


  • 2
    L

    @dchen0215 said in My accepted Java solution:

    prev.next = cur;
    prev = cur;

    cool solution, and change to this, maybe easier to unstand

    prev.next = cur;
    prev = prev.next;


  • 0
    L

    @rushikesh.rush
    i think it means

    if ( l1!=null) {
    l1=l1.next
    }


Log in to reply
 

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