两数之和
链接：
https://leetcode.cn/problems/add-two-numbers/
题解
两数相加，需要返回头指针，所以就两个指针head和tail来进行表示，最后返回head，计算过程用 tail作用。
因为两个链表可能长度不一样，所以while的条件很重要。然后就是对于其中某个指针有没有值的判断，用三目运算符。接着就是对于头指针是否为空，因为初始化的时候头指针和尾指针都是空指针。然后是原来两个指针的更新逻辑。以及进位逻辑。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = nullptr;
ListNode* tail = nullptr;
int carry = 0;
while (l1 || l2) {
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + carry;
if (!head) {
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
if (carry > 0) {
tail->next = new ListNode(carry);
}
}
return head;
}
};
|
反转链表
https://leetcode.cn/problems/reverse-linked-list/submissions/575965011/
代码如下：
用三个指针实现，curr,next和prev，curr指向当前，next指向下一个，prev指向curr的前一个，（一开始curr指向传入的头指针）然后prev和next是空指针，更新逻辑是：
- 保存当前节点curr的下一个指针为next
- 令当前节点curr指向前一个节点prev
- 先将prev更新为curr
- 后将当前指针更新为之前保存的next
- 直到当前指针为空，因为在循环中更新了，所以返回prev
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev=nullptr;
ListNode* next=nullptr;
ListNode* current=head;
while(current!=nullptr){
next=current->next;
current->next=prev;
prev=current;
current=next;
}
return prev;
}
};
|
C++中一个结构体的对象可以用.或者->访问，但是一个结构体指针的对象只能用->，不能用.
C++中类的结尾要有分号
删除单向链表的倒数第n个节点
双指针法
思路是用两个距离为n的指针，每次同时更新这两个指针，当后面的指针为空的时候前面的指针刚好到达倒数第n个。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* tail=head;
ListNode* front=head;
ListNode* del=head;
for(int i=0;i<n;i++){
tail=tail->next;
}
while(tail!=nullptr){
front=del;
del=del->next;
tail=tail->next;
}
if(del==head){
return head->next;
}
front->next=del->next;
return head;
}
};
|
合并两个升序链表
合并两个升序链表
解法一：遍历
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode*p1=list1;
ListNode*p2=list2;
ListNode dummy(0);
ListNode* result=&dummy;
while(p1&&p2){
if(p1->val<p2->val){
result->next=p1;
p1=p1->next;
result=result->next;
}else{
result->next=p2;
p2=p2->next;
result=result->next;
}
}
p1==nullptr?result->next=p2:result->next=p1;
return dummy.next;
}
};
|
解法二：递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1){
return list2;
}
else if(!list2){
return list1;
}
else if(list1->val<list2->val){
list1->next=mergeTwoLists(list2,list1->next);
return list1;
}
else{
list2->next=mergeTwoLists(list1,list2->next);
return list2;
}
}
};
|
两两交换链表中的节点
两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
迭代法
思路：用一个哑结点 dummyHead放在头节点前，再用一个指针 tmp去遍历，从dummyHead开始，终止条件是指针tmp指向空或者下一个指针指向空。
在循环的内部，可以初始化两个节点，指向tmp的下一个和下下一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy=new ListNode(0);
dummy->next=head;
ListNode*tmp=dummy;
while((tmp->next!=nullptr)&&(tmp->next->next!=nullptr)){
ListNode*back=tmp->next;
ListNode*forward=back->next;
back->next=forward->next;
forward->next=back;
tmp->next = forward;
tmp=back;
}
return dummy->next;
}
};
|
递归
为了得到交换后的链表，我们可以认为，递归的条件是递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return head;
}
ListNode* newhead=head->next;
head->next=swapPairs(newhead->next);
newhead->next=head;
return newhead;
}
};
|
求数组中和为目标值的下标
方法一（暴力遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n=nums.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(nums[i]+nums[j]==target){
return {i,j};
}
}
}
return {};
}
};
|
方法二（哈希表）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>myHash;
for(int i=0;i<nums.size();i++){
auto it=myHash.find(target-nums[i]);
if(it!=myHash.end()){
return {i,it->second};
}
myHash[nums[i]]=i;
}
return {};
}
};
|
35.搜索插入位置
[https://leetcode.cn/problems/search-insert-position/description/]
二分法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
};
|
