Listen to the sediment spread… Pay attention to wechat public number [Java], help you give up the path of programming!
An algorithm problem every day, explain their own problem-solving ideas and implementation; You are welcome to comment or give your thoughts on how to solve the problem; Also can comment want me to explain which problem!
The title
You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node.
You add the two numbers and return a linked list representing the sum in the same form.
You can assume that neither of these numbers will start with 0, except for the number 0.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output:,0,8 [7]
Explanation: 342 + 465 = 807.
Example 2:
Input: L1 = [0], L2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9], l2 = [9,9,9,9]
Output:,9,9,9,0,0,0,1 [8]
Source: LeetCode link: leetcode-cn.com/problems/ad…
A, thinking
When two numbers are added, they are generally added from the lowest digit to the highest digit. If there is a carry, the carry must be added to the highest digit.
Therefore, you can use this simple algorithm, after the same digit addition, use the new node to save the ones digit value, use the carry variable to save the tens digit value;
Considering the problem of storage space and whether the original linked list data can be changed, two algorithms can be implemented:
- All nodes of the new linked list are newly generated when the original linked list data cannot be changed.
- If the original linked list data can be changed, the nodes of the new linked list can reuse the nodes of the original linked list.
Second, algorithm implementation
package com.nobody;
/** * Node class */
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString(a) {
return "ListNode{" + "val=" + val + '} '; }}/ * * *@DescriptionYou are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node. * Add the two numbers and return a linked list representing the sum in the same form. You can assume that neither of these numbers will start with 0, except for the number 0. * Original link: https://leetcode-cn.com/problems/add-two-numbers/ *@Author Mr.nobody
* @Date 2021/1/22
* @Version1.0 * /
class Solution {
// Each node of the new list is newly generated (without changing the original list data)
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Table header, mainly for the next node to connect to keep the same operation
ListNode headNode = new ListNode();
/ / the cursor
ListNode cursor = headNode;
/ / carry
int temp = 0;
// All the data in both lists is traversed at the same time to ensure that the data in the same position in both lists are added together
while (null! = l1 ||null! = l2 ||0! = temp) {// The current node (digit) is not empty
if (null! = l1) {// Add the value of this node
temp += l1.val;
// point to the next node
l1 = l1.next;
}
if (null! = l2) {// Add the value of this node
temp += l2.val;
// point to the next node
l2 = l2.next;
}
// Generate a new node, keeping the added bits
cursor.next = new ListNode(temp % 10);
// The cursor points to a new node in a new linked list
cursor = cursor.next;
// Retain the tens place value after the addition.
temp = temp / 10;
}
// Return the actual header
return headNode.next;
}
// Save storage space by using the nodes of the original linked list (if you can change the data of the original linked list)
public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
// Table header, mainly for the next node to connect to keep the same operation
ListNode headNode = new ListNode();
/ / the cursor
ListNode cursor = headNode;
// carry, save the sum of the two low values of each carry
int temp = 0;
// All the data in both lists is traversed at the same time to ensure that the data in the same position in both lists are added together
while (null! = l1 ||null! = l2) {// The current node (digit) is not empty
if (null! = l1) {// Add the value of this node
temp += l1.val;
// The value of the current node is no longer used, you can use this node as a new linked list node to save storage space (if l2 node is not empty, it will be replaced by L2 node)
cursor.next = l1;
// point to the next node
l1 = l1.next;
}
if (null! = l2) {// Add the value of this node
temp += l2.val;
// The value of the current node is no longer useful. You can use this node as a new list node to save storage space
cursor.next = l2;
// point to the next node
l2 = l2.next;
}
// The cursor points to a new node in a new linked list
cursor = cursor.next;
// Keep the ones digit
cursor.val = temp % 10;
// Retain the tens place value after the addition.
temp = temp / 10;
}
// If the last run is not empty, this carry is required
if (0! = temp) { cursor.next =new ListNode(temp);
}
// Return the actual header
return headNode.next;
}
public static void main(String[] args) {
ListNode l1 = new ListNode(0);
l1.next = new ListNode(1);
l1.next.next = new ListNode(8);
// Print the original list 1
ListNode l1temp = l1;
while (null! = l1temp) { System.out.print(l1temp +"");
l1temp = l1temp.next;
}
System.out.println();
ListNode l2 = new ListNode(0);
l2.next = new ListNode(9);
// Print the original list 2
ListNode l2temp = l2;
while (null! = l2temp) { System.out.print(l2temp +"");
l2temp = l2temp.next;
}
System.out.println();
// Prints the new list after the addition
ListNode newNode = addTwoNumbers1(l1, l2);
while (null! = newNode) { System.out.print(newNode +""); newNode = newNode.next; }}}Copy the code
Output result:
ListNode{val=0} ListNode{val=1} ListNode{val=8}
ListNode{val=0} ListNode{val=9}
ListNode{val=0} ListNode{val=0} ListNode{val=9}
Copy the code
Leetcode execution result:
Three, the upper and lower chapters
LeetCode – the sum of two numbers
Implementation of LeetCode – array form integer addition algorithm