CODEWITHSUNDEEP
javaalgorithm
Jacobo Escobar
Jacobo Escobar

Reputation: 1

Add Two Numbers: LeetCode - Java solution

I'm trying to figure out the Java solution for the problem Add Two Numbers from Leetcode.

Below is LeetCode's Java solution but I have questions:
Why is dummyHead.next returned as the result when in the while loop never assigned the number to this listnode?
How works curr assign to dummyHead if curr is equal to dummyHead not the other way?

class Solution {
    // Add Two Numbers (Java improved)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        return dummyHead.next;
    }
}

Upvotes: 0

Views: 1398

Answers (3)

Old Dog Programmer
Old Dog Programmer

Reputation: 1251

The quick explanation is there is a chain of nodes, provided by next in each Node. dummyHead is used to point to the first node of the chain. Initially, dummyHead and curr are the same node. They will be the same node until either one is reassigned.

The results are to be returned as a linked list, the structure / code of which is described in the comments above the solution header.

The correct code needs to return the head (first node) of the singly linked list. The head node will link to the 2nd node, the 2nd node will link to the 3rd, and so on for as many nodes needed. The last node will link to null.

    ListNode dummyHead = new ListNode(0);
    ListNode curr = dummyHead;

dummyHead and curr are reference types. At this point, they are two names for the same Object: val in one is the same as val in the other. next in one is the same as next in the other. What happens when the following line is executed?

    curr.next = new ListNode(sum % 10);

next in dummyHead and next in curr point to the newly created Node. Remember, in the initial iteration, they are two names for the same object.

What happens when the following line is executed?

    curr = curr.next;

Now, curr points to the newly created Node.
dummyHead still points to the first node -- the one to be returned.
They no longer refer to the same Object.
And next in dummyHead points to the 2nd node in the list, or null if the list has only the one node.

So, as the iteration progresses, a new Node is created. The last node in the chain, called curr, is linked to the new node. Then, curr is updated to point to the new node.
And dummyHead continues to point to the first node.

Upvotes: 1

Chintan Trivedi
Chintan Trivedi

Reputation: 191

LinkedList always have two fields: one is value and second one is the pointer to next node. If it's last node than next points to null.

Here in the code you mentioned:

Line 1-3 : generate new result linkedlist head using dummyHead and assign a variable curr to that head for moving and assigning purposes.

Carry is only used to check if sum is greater than 10 will be forwarded to next iterations.

In while loop: we are looping untill all the values become null.

If one or two value is null than we are assiging 0 using ternary oprator, and generating sum.

After sum is generated modules will be consider as carry and divison will be consider as value of node.

After loop is done we are returning head of linkedlist using the variable we have created.

It should be dummyHead.next as dummyHead is the node 0 we have intialized, but actual result starts from the next value.

Upvotes: 0

Elliott Frisch
Elliott Frisch

Reputation: 201447

The important bit is new ListNode(0) that is what dummyHead and curr start with. Not different ListNode(s). So if you swapped curr and dummyHead like

ListNode curr = new ListNode(0);
ListNode dummyHead = curr;

it would behave the same way.

Upvotes: 2

Related Questions