Question (adding two numbers)
gives you two non-empty linked lists representing two non-negative integers. They are stored in reverse order per digit, and each node can only store one digit.
Please add two numbers and return a linked list representing the sum in the same form.
You can assume that neither number starts with 0 except for the number 0.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
hint:
The number of nodes in each linked list is in the range [1, 100]
0 <= Node.val <= 9
The title data ensures that the numbers represented by the list do not contain leading zeros
Source: LeetCode
Link: https://leetcode.cn/problems/add-two-numbers
The copyright belongs to Lingkou Network. For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.
code
(recursive)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(l1==nullptr)
return l2;
if(l2==nullptr)
return l1;
int sum=l1->val+l2->val;
if(sum>9)
return new ListNode(sum-10,addTwoNumbers(new ListNode(1,nullptr),addTwoNumbers(l1->next,l2->next)));
else
return new ListNode(sum,addTwoNumbers(l1->next,l2->next));
}
};
recursion 2
class Solution {
public:
ListNode* addNumbers(ListNode* l1, ListNode* l2,int res) {
if(l1==nullptr&&l2==nullptr&&res==0)
return nullptr;
ListNode* child=new ListNode();
int value=0;
if(l1!=nullptr){
value+=l1->val;
}
if(l2!=nullptr){
value+=l2->val;
}
value+=res;
child->val=value%10;
value=value/10;
child->next=addNumbers(l1==nullptr?nullptr:l1->next,l2==nullptr?nullptr:l2->next,value);
return child;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return addNumbers(l1==nullptr?nullptr:l1,l2==nullptr?nullptr:l2,0);
}
};
non-recursive
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(l1==nullptr)
return l2;
if(l2==nullptr)
return l1;
ListNode *head=new ListNode(0);
ListNode *cur=head;
int jinwei=0,num=0;
while(l1&&l2){
num=(l1->val+l2->val+jinwei)%10;
jinwei=(l1->val+l2->val+jinwei)/10;
ListNode *temp=new ListNode(num);
cur->next=temp;
cur=temp;
l1=l1->next;
l2=l2->next;
}
while(l1){
num=(l1->val+jinwei)%10;
jinwei=(l1->val+jinwei)/10;
ListNode *temp=new ListNode(num);
cur->next=temp;
cur=temp;
l1=l1->next;
}
while(l2){
num=(l2->val+jinwei)%10;
jinwei=(l2->val+jinwei)/10;
ListNode *temp=new ListNode(num);
cur->next=temp;
cur=temp;
l2=l2->next;
}
if(jinwei){
cur->next=new ListNode(1);
}
return head->next;
}
};
Title (pow(x, n))
Implements pow(x, n) , a function that computes x raised to the nth power of an integer (ie, xn ).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
hint:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
Source: LeetCode
Link: https://leetcode.cn/problems/powx-n
The copyright belongs to Lingkou Network. For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.
I wrote it myself, and it times out when the number is extremely large~
class Solution {
public:
double myPow(double x, int n) {
if(n==1)
return x;
else if(n==-1)
return 1/x;
else if(n<-1)
return 1/x*myPow(x,n+1);
else
return x*myPow(x,n-1);
}
};
Reference code~
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) {
return 1.0;
} else if ((n & 1) == 0) {
return myPow(x * x, n / 2);
} else {
return (n > 0 ? x : 1.0 / x) * myPow(x * x, n / 2);
}
}
};
Topic (rearranged linked list)
Given a head node head of a singly linked list L, the singly linked list L is represented as:
L0 → L1 → ... → Ln - 1 → Ln
Please rearrange it to become:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → ...
You can't just change the value inside the node, but actually need to exchange the node.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
hint:
The length of the linked list is in the range [1, 5 * 104]
1 <= node.val <= 1000
Source: LeetCode
Link: https://leetcode.cn/problems/reorder-list
The copyright belongs to Lingkou Network. For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.
code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(head->next==nullptr||head==nullptr||head->next->next==nullptr)
return ;
ListNode *temp=head;
ListNode *pre=new ListNode();
while(temp->next){
pre=temp;
temp=temp->next;
}
temp->next=head->next;
head->next=temp;
pre->next=nullptr;
reorderList(temp->next);
}
};