This is the fifth day of my participation in the August Wen Challenge.More challenges in August
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.
Tip:
- The number of nodes in each linked list is in the range
[1, 100]内 0 <= Node.val <= 9- The question data ensures that the numbers represented in the list do not contain leading zeros
Source: LeetCode link: leetcode-cn.com/problems/ad…
Example:
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4] output: [7,0,8] explanation: 342 + 465 = 807.Copy the codeExample 2:
Input: l1 =,9,9,9,9,9,9 [9], l2 =,9,9,9 [9] output:,9,9,9,0,0,0,1 [8]Copy the codeA. the b. the C. the D. the
Main contents of the title:
- Given two non-empty linked lists
- A linked list stored in reverse order
- The positive sequence of 2 -> 4->3 is
342
- The positive sequence of 2 -> 4->3 is
- When the two numbers are added, a new linked list is returned
- It’s also a linked list in reverse order
Details:
- Both lists are non-empty
- Two non-negative integers
- Neither number starts with a zero
- The numbers are arranged in reverse order, with the first node representing the least significant integer
- They don’t specify the range of integers, and that’s an easy point to ignore
Implementation scheme
- 1 – List to numbers, add, and then to character array, output new list
- Profiteer cracking 2 – List to number, add, convert list
- Optimization solution – list traversal directly, the corresponding position of the number added, directly return to the new list
note
Methods 1 and 2 use a completely stupid method to implement the function, but do not run the test when leetCode is submitted. BigInteger
Implementation scheme 1: Violent profit cracking 1 – linked list to number, add, and then turn character array, output new linked list
Implementation logic:
-
L1 and L2 perform the same steps:
- Loop through the linked list, converting elements in reverse order to integers
-
Add two integers
-
Convert to a String array
-
Loop through the String array to print a new list in reverse order
public ListNode addTwoNumbersOne(ListNode l1, ListNode l2) {
// Convert lists to numbers
long num1 = 0;
// Number of digits: 0 represents the ones digit and 1 represents the tens digit
int square1 = 0;
while(l1 ! =null) {
num1 += (long) l1.val * Math.pow(10, square1);
l1 = l1.next;
square1++;
}
long num2 = 0;
int square2 = 0;
while(l2 ! =null) {
num2 += (long) l2.val * Math.pow(10, square2);
l2 = l2.next;
square2++;
}
long sumNum = num1 + num2;
// If the sum is 0, the new list is returned directly
if (sumNum == 0) {
return new ListNode(0);
}
// Convert to an array of strings
String[] strArr = String.valueOf(sumNum).split("");
ListNode newNode = null;
// Loop through to form a new reverse linked list
for (String aStr : strArr) {
if (newNode == null) {
newNode = new ListNode(Integer.parseInt(aStr));
} else {
newNode = newListNode(Integer.parseInt(aStr), newNode); }}return newNode;
}
Copy the codeImplementation scheme 2: Violent profit cracking 2 – linked list to number, add, conversion linked list
Implementation logic: optimize the violent profit solution, remove the integer to string array, reduce space complexity
- Loop through the linked list, converting elements in reverse order to integers
- Add two integers
- Using mathematical thinking, logarithm mod, can obtain the value of each, create a new linked list
public ListNode addTwoNumbersTwo(ListNode l1, ListNode l2) {
long num1 = 0;
int square1 = 0;
while(l1 ! =null) {
num1 += (long) l1.val * Math.pow(10, square1);
l1 = l1.next;
square1++;
}
long num2 = 0;
int square2 = 0;
while(l2 ! =null) {
num2 += (long) l2.val * Math.pow(10, square2);
l2 = l2.next;
square2++;
}
long sumNum = num1 + num2;
ListNode head = new ListNode(); // Create a new list with an empty node in the head
ListNode cur = head;
if (sumNum == 0) {
return new ListNode(0);
}
// loop over the sum of the two numbers
while (sumNum > 0) {
// Get the lowest value each time you mod an integer
int val = (int) sumNum % 10;
// Add to the list
cur.next = new ListNode(val);
cur = cur.next;
// Remove the least significant value of the integer
sumNum = sumNum / 10;
}
return head.next;
}
Copy the codeImplementation scheme 3: direct traversal of the linked list, add the corresponding position numbers, directly return the new linked list
Implementation logic:
- Iterate over two linked lists at the same time, add the number in the same position of the two linked lists to the new linked list
- Set carry
- When each number is added, a carry is added to prevent a carry
- After the list has been traversed, determine whether there are more carries, and append more carries at the end
Core calculation formula: sum = last digit of x + last digit of y + carry
public ListNode addTwoNumbersThree(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while(l1 ! =null|| l2 ! =null) {
// Check whether the bit in the list has a value, if no value, return zero
intx = l1 ! =null ? l1.val : 0;
inty = l2 ! =null ? l2.val : 0;
// Add two list bits and add carry values
int temp = x + y + carry;
// Put the cumulative value into the new linked list
if (head == null) {
head = tail = new ListNode(temp % 10);
} else {
tail.next = new ListNode(temp % 10);
tail = tail.next;
}
// Get the carry value
carry = temp / 10;
l1 = l1 == null ? l1 : l1.next;
l2 = l2 == null ? l2 : l2.next;
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
Copy the codeMaking the address
Case address