Question

Formatted question description: https://leetcode.ca/all/2.html

2	Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in
reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a
linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

@tag-linkedlist

Algorithm

Create a new linked list, and then push the input two linked lists from the beginning to the back, add every two, and add a new node to the back of the new linked list.

In order to prevent the two input linked lists from being empty at the same time, we create a dummy node, and add the new nodes generated by the addition of the two nodes to the dummy node in order.

Since the dummy node itself cannot be changed, a pointer is used cur to point to the last node of the new linked list. Ok, you can start to add the two linked lists.

This problem is good because the lowest bit is at the beginning of the linked list, so you can directly add them in order from low to high while traversing the linked list. The condition of the while loop, as long as one of the two linked lists is not an empty row, since the linked list may be empty, when taking the current node value, judge first, if it is empty then value is 0, otherwise take the node value.

Then add the two node values ​​together, and add carry. Then update carry, directly sum/10, and then create a new node with sum%10 as the value, connect it to the back of cur, and then move cur to the next node.

Then update the two nodes, if they exist, point to the next location. After the while loop exits, the highest carry issue needs to be dealt with specially. If carry is 1, then another node with value 1 is created.

Code

Java

public class Add_Two_Numbers {

	public class Solution {
	    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	        if (l1 == null || l2 == null) {
	            return l1 == null ? l2 : l1;
	        }

	        // boolean style, 0 or 1
	        int carry = 0;

	        ListNode dummy = new ListNode(0);
	        ListNode dummyCopy = dummy;

	        while (l1 != null || l2 != null) {
	            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;

	            // append to result list
	            dummy.next = new ListNode(sum % 10);
	            carry = sum >= 10 ? 1 : 0;

	            // move to next node
	            l1 = l1 == null ? null : l1.next;
	            l2 = l2 == null ? null : l2.next;
	            dummy = dummy.next;
	        }

	        // @note: I missed final check
	        if (carry == 1) {
	            dummy.next = new ListNode(carry);
	        }

	        return dummyCopy.next;
	    }
	}

}

All Problems

All Solutions