前言
LeetCode 2. 两数相加（**）
题目类型
- 链表
题目链接
思路
跟加法逻辑一下 保存进位carry
AC代码
/**
* 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) {
ListNode* res = new ListNode(-1);
ListNode* cur = res;
int carry = 0;
while(l1 || l2)
{
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = carry + n1 + n2;
carry = sum / 10;
cur -> next = new ListNode(sum % 10);
cur = cur -> next;
if (l1) l1 = l1 -> next;
if (l2) l2 = l2 -> next;
}
if (carry) cur -> next = new ListNode(carry);
return res->next;
}
};
LeetCode 19. 删除链表的倒数第N个节点（**）
题目类型
- 链表的删除
- 双指针应用
题目链接
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
思路
注意加个头结点防止只有一个元素，而要删除该元素
方法一：数学方法
- p指向头结点
- 让p走k - n - 1步即可到达删除结点的前驱，其中k为链表长度
方法二：双指针（时间更快）
- 都指向头结点
- q走n + 1步
- p q同时走 当q到达尾部NULL时候，p指向倒数第n个数的前驱
AC代码1
方法一：
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy_head = new ListNode(-1);
dummy_head->next = head;
int k = 0;
auto p = dummy_head;
while(p->next)
{
k ++;
p = p->next;
}
auto q = dummy_head;
for (int i = 0; i < k - n; i ++) q = q->next;
q->next = q->next->next;
return dummy_head->next;
}
};
AC代码2
方法二：时间更快
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy_head = new ListNode(-1);
dummy_head->next = head;
ListNode* p = dummy_head;
ListNode* q = dummy_head;
// 先让q走n + 1步 因为前面有虚拟结点
for (int i = 0; i < n + 1; i ++) q = q->next;
while (q)
{
p = p->next;
q = q->next;
}
p->next = p->next->next;
return dummy_head->next;
}
};
LeetCode 21. 合并两个有序链表（*）
题目类型
- 链表
- 升序序列的合并问题
题目链接
思路
- 遍历两个链表，每次选择最小的数添加到新链表的尾部即可
- 最后两个链表可能存在一个还有未插入序列，将该序列插入即可，这里有两种写法，一种是我自己写的不够精简，y总的写法比较精简（有时候看y总代码真是有种看艺术品感觉）
while (l1) cur->next = l1, l1 = l1->next, cur = cur->next;
while (l2) cur->next = l2, l2 = l2->next, cur = cur->next;
cur->next = (l1 == NULL ? l2 : l1);
AC代码
/**
* 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (l1 && l2)
{
if (l1->val < l2->val)
{
cur->next = l1;
l1 = l1->next;
}
else
{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
// while (l1) cur->next = l1, l1 = l1->next, cur = cur->next;
// while (l2) cur->next = l2, l2 = l2->next, cur = cur->next;
cur->next = (l1 == NULL ? l2 : l1);
return dummy->next;
}
};
LeetCode 23. 合并K个排序链表（***）
题目类型
- 链表
- 小根堆
- k路合并问题
题目链接
思路
此题和21题类似，只不过21题是2路合并，该题是k路合并，思路如下：
- 每次取k个链表中首部最小的那个数
- 将该数插到结果链表
- 直到所有链表都插入完
很容易得知该时间复杂度为$O(K*N)$
此处可以用小根堆做优化
/**
* 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:
struct Cmp
{
bool operator()(ListNode* a, ListNode* b)
{
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
auto dummy = new ListNode(-1), p = dummy;
// 将每个链表的第一个元素（也就是最小数）放入堆中
for (auto l : lists) if (l) heap.push(l);
while (heap.size())
{
// 取堆顶
auto t = heap.top();
heap.pop();
p->next = t;
p = t;
if (t->next) heap.push(t->next);
}
return dummy->next;
}
};
LeetCode 24. 两两交换链表中的节点（**）
题目类型
- 链表
- 交换问题
题目链接
思路
对于p->a->b，其中p为虚拟头结点
交换ab只需要
p->next = b;
a->next = b->next;
b->next = a;
AC代码
/**
* 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* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
while (p->next && p->next->next)
{
auto a = p->next, b = a->next;
p->next = b;
a->next = b->next;
b->next = a;
p = a;
}
return dummy->next;
}
};
LeetCode 25. K 个一组翻转链表（***）
题目类型
- 链表
- k组翻转
题目链接
思路
此时看起来不难，实际实现的时候很容易出错，建议多刷几次
- 每次检验是否下一组足够k个元素，不够则break 够的话继续往下执行
- 对于 p->a->b->c->d 从a开始进行k-1次循环反转指针,而且注意在反转指针之前要把b->next存起来
auto c = b->next, b->next = a
- k-1次之后（也就是该组已经反转成功后） 此时将p->next->next = b，落到了下一组以b为开始的反转的前一个结点（可以看做是虚拟结点）
- 继续以上操作
AC代码
/**
* 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* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
for (auto p = dummy;;)
{
// 判断是否满足k个元素
auto q = p;
for (int i = 0; i < k && q; i ++) q = q->next;
if (!q) break; // 不满足直接跳出
// 满足有k个元素
auto a = p->next, b = a->next;
for (int i = 0; i < k - 1; i ++) // 内部交换k - 1次
{
auto c = b->next;
b->next = a;
a = b, b = c;
}
auto t = p->next;
p->next = a;
t->next = b;
p = t;
}
return dummy->next;
}
};
LeetCode 82. 删除排序链表中的重复元素 II
题目类型
- 删除操作
题目链接
https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
思路
这里解法一是自己写的方法
解法二是y总的，y总代码比较精简，y总的题解：https://www.acwing.com/solution/content/166/
AC代码一
// 朴素法
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
// 创建虚拟头结点
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *cur = dummy;
// 遍历
while (cur->next && cur->next->next)
{
if (cur->next->val == cur->next->next->val)
{
int x = cur->next->val;
while (cur->next && cur->next->val == x)
{
cur->next = cur->next->next;
}
}
else
{
cur = cur->next;
}
}
return dummy->next;
}
};
AC代码二
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* p = dummy;
while (p->next)
{
ListNode* q = p->next->next;
while (q && q->val == p->next->val) q = q->next;
if (p->next->next == q) p = p->next;
else p->next = q;
}
return dummy->next;
}
};
LeetCode 83. 删除排序链表中的重复元素
题目类型
- 删除
题目链接
https://leetcode.cn/problems/remove-duplicates-from-sorted-list/submissions/
思路
比较简单看代码就可以
AC代码
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* p = head;
while (p)
{
ListNode* q = p->next;
if (q && q->val == p->val)
{
p->next = q->next;
}
else
{
p = p->next;
}
}
return head;
}
};
LeetCode 86. 分隔链表
题目类型
- 分治
题目链接
https://www.acwing.com/activity/content/problem/content/2435/
思路
- 定义两个链表，一个存储小于x的数，一个存储大于x的数
- 从头往后遍历分别插入两个链表
- 最后将两个链表归并
AC代码
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
// 定义两个头结点
ListNode* l_head = new ListNode(-1), *r_head = new ListNode(-1);
ListNode* lt = l_head, *rt = r_head;
for (auto p = head; p; p = p->next)
{
if (p->val < x)
{
lt->next = p;
lt = p;
}
else
{
rt->next = p;
rt = p;
}
}
lt->next = r_head->next;
rt->next = nullptr;
return l_head->next;
}
};
LeetCode 92. 反转链表 II
题目类型
- 链表逆转
题目链接
思路
这道题一点点绕 我刚开始也想不出来 第一天大概写了一下然后报错 我就跳过写第二题了
代码思路看下面AC代码的注释即可
AC代码
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (left == right) return head;
//创造头结点
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* p = dummy;
// p找到left的前驱结点 a为left结点的前驱结点 b为left结点 c为left结点的下个结点
for (int i = 0; i < left - 1; i ++) p = p->next;
ListNode* a = p, *b = a ->next, *c = b->next;
// 将left到right的指针反向
for (int i = left; i < right; i ++) // 内部进行right-left次逆转即可
{
ListNode* d = c->next;// 这里要保存好c的next指针 因为c要反向指向b 会丢失下一个结点
c->next = b;
// 更新下一次翻转所需要的工作指针
b = c, c = d;
}
// 从left 到 right 已经反转 接下来处理好原来left的前驱和right的后继
a->next->next = c; // 此时c是right的下一个结点 只需要把left点（即a->next）的next指向c即可
a->next = b; // 此时b是right点 只需要把left的前驱结点（即a）的next指向b
return dummy->next;
}
};
LeetCode 109. 有序链表转换二叉搜索树
题目类型
- 二叉树
题目链接
https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/
思路
每次以链表的中点为根节点，生成二叉树，可以递归处理
AC代码
class Solution {
public:
// 寻找链表的(left, right)中点 用快慢指针
ListNode* getMidNode(ListNode* left, ListNode* right)
{
ListNode* fast = left;
ListNode* slow = left;
while (fast != right && fast->next != right)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
// 以left和right的中点建立一棵二叉子树
TreeNode* buildBST(ListNode* left, ListNode* right)
{
if (left == right) return nullptr;
// 寻找left到right的中点
ListNode* mid = getMidNode(left, right);
// 以mid为中点转变为一棵二叉树
TreeNode* root = new TreeNode(mid->val);
root->left = buildBST(left, mid);
root->right = buildBST(mid->next, right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
return buildBST(head, nullptr);
}
};
LeetCode 114. 二叉树展开为链表
题目类型
- 链表二叉树
题目链接
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
思路
看LeetCode的题解就好了 很详细
AC代码一 遍历树
class Solution {
public:
void flatten(TreeNode* root) {
while (root)
{
TreeNode* p = root->left;
if (p)
{
TreeNode* q = p;
while (q->right) q = q->right;
q->right = root->right;
root->right = p;
root->left = nullptr;
}
root = root->right;
}
}
};
AC代码二 先序遍历
LeetCode 116. 填充每个节点的下一个右侧节点指针
题目类型
- BFS
题目链接
https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/submissions/
思路
- 遍历二叉树的每一层
- 对于每一层的结点A和下一个结点B，将A的左孩子的next指向A的右孩子，如果B存在，将A的右孩子指向B的左孩子
AC代码
class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;
// 先存下根节点
Node* source = root;
// 遍历树的每一层
while (root->left)
{
// 遍历每一层的每一个结点
for (Node* p = root; p; p = p->next)
{
// 同一父节点 直接让左孩子指向右孩子
p->left->next = p->right;
// 不同父节点 让前一个父节点的右孩子指向后一个父节点的左孩子
// 如果没有下一个结点则无需添加
if (p->next) p->right->next = p->next->left;
else p->right->next = NULL;
}
root = root->left;
}
return source;
}
};
LeetCode 117. 填充每个节点的下一个右侧节点指针 II
题目类型
- BFS
题目链接
https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii
思路
与前一题不同，该题遍历每一层的时候需要创建head和tail两个指针
head是用来使下一层的结点连接到一条链表中，tail是用来指向该链表的尾结点用于插入
最后更新下一层 cur
AC代码
class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;
Node* cur = root;
while (cur)
{
Node* head = new Node(-1);
Node* tail = head;
// 遍历该层的每一个结点
for (Node* q = cur; q; q = q->next)
{
if (q->left) tail = tail->next = q->left;
if (q->right) tail = tail->next = q->right;
}
cur = head->next;
}
return root;
}
};
LeetCode 141. 环形链表
题目类型
- 判断环
题目链接
思路
方法一：
遍历链表，使用哈希表记录访问过的点，如果访问的点出现在哈希表中说明存在环
方法二：
快慢指针，如果slow 和 fast相遇说明存在环
AC代码—哈希表
class Solution {
public:
bool hasCycle(ListNode *head) {
// 使用哈希表存储访问过的点
unordered_set<ListNode*> hash;
ListNode* p = head;
while (p)
{
if (hash.count(p)) return true;
hash.insert(p);
p = p->next;
}
return false;
}
};
AC代码—快慢指针
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;
ListNode* slow = head, * fast = head->next;
while (slow != fast)
{
if (!fast || !fast->next) return false;
fast = fast->next->next;
slow = slow->next;
}
return true;
}
};
LeetCode 143. 重排链表
题目类型
- 链表排序
题目链接
思路
方法一：
- 由于链表没有随机访问的特性，所以将链表存储在线性表r中
- 使用双指针对链表重新排序
时间复杂度O(n) 空间复杂度O(n)
方法二：此题可以分为三个子问题
- 寻找链表中间 参考 LeetCode 876
- 反转后半段的链表 参考 LeetCode 206
- 使用两个指针，交叉拼接拼接两个链表
AC代码一
class Solution {
public:
void reorderList(ListNode* head) {
if (!head) return ;
vector<ListNode*> r;
while (head)
{
r.push_back(head);
head = head->next;
}
int i = 0, j = r.size() - 1;
while (i < j)
{
r[i ++]->next = r[j];
if (i == j) break;
r[j --]->next = r[i];
}
r[i]->next = nullptr;
}
};
AC代码二
class Solution {
public:
// 寻找链表的中点
ListNode* searchMid(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// 反转链表
ListNode* reverseList(ListNode* head)
{
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur)
{
ListNode* curTmp = cur->next;
cur->next = prev;
// 保存好下一次反转的前驱结点和下一次反转的当前节点cur
prev = cur, cur = curTmp;
}
return prev;
}
// 交叉合并链表
void mergeList(ListNode* l1, ListNode* l2)
{
while(l1 && l2)
{
ListNode* l1_tmp = l1->next;
ListNode* l2_tmp = l2->next;
l1->next = l2, l1 = l1_tmp;
l2->next = l1, l2 = l2_tmp;
}
}
void reorderList(ListNode* head) {
ListNode* mid = searchMid(head);
// 划分两个链表
ListNode* l1 = head;
ListNode* l2 = mid->next;
mid->next = nullptr;
// 先反转链表
l2 = reverseList(l2);
// 再合并链表
mergeList(l1, l2);
}
};
LeetCode 146. LRU缓存机制
题目类型
- 链表插入
- 链表删除
- 双链表
- 哈希表
题目链接
思路
此题难度稍微一点点大，主要是题目要求get和put要O(1)，也就是说插入删除查找要O(1) 复杂度，所以利用哈希表和双链表来实现缓存的LRU
- 可以利用哈希表当做缓存，查找可以实现O(1)
- 双链表当做缓存的时间队列（最近访问放最前面，最后访问放最后），插入和删除由于有头指针和尾指针，也可以实现O(1)
其他就是常见的业务需求了
AC代码
class LRUCache {
public:
struct Node
{
int key, val;
Node* left, *right;
Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {};
} *L, *R;
unordered_map<int, Node*> hash;
void insert(Node *p)
{
p->right = L->right;
p->left = L;
L->right->left = p;
L->right = p;
}
void remove(Node* p)
{
p->right->left = p->left;
p->left->right = p->right;
}
int n;
LRUCache(int capacity) {
n = capacity;
L = new Node(-1, -1), R = new Node(-1, -1);
L->right = R;
R->left = L;
}
int get(int key) {
// 若不在缓存
if (hash.count(key) == 0) return -1;
auto p = hash[key];
remove(p), insert(p);
return p->val;
}
void put(int key, int value) {
// 若在缓存中 覆盖val值 并更新链表
if (hash.count(key))
{
auto p = hash[key];
p->val = value;
remove(p), insert(p);
}
else
{
if (hash.size() == n) // 如果缓存满了 删除最少访问的那个
{
auto p = R->left;
remove(p);
hash.erase(p->key);
}
auto p = new Node(key, value);
insert(p), hash[key] = p;
}
}
};
LeetCode 147. 对链表进行插入排序
题目类型
- 插入排序
题目链接
思路
看起来简单，我写的时候容易被指针搞乱，基础还是不扎实
- 创建虚拟结点dummy，用于存放结果
- p指针遍历原链表，cur遍历结果链表
- 寻找第一个比p大的结点，将cur插在p的前面
AC代码
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode* dummy = new ListNode(-1);
// 遍历链表
for (auto p = head; p;)
{
// 从结果链表的开头也就是dummy开始往后寻找
auto cur = dummy, p_next_tmp = p->next;
// 寻找结果链表的第一个大于p的结点 将p放在该结点的前面
while (cur->next && p->val >= cur->next->val) cur = cur->next;
p->next = cur ->next;
cur->next = p;
p = p_next_tmp;
}
return dummy->next;
}
};
LeetCode 148. 排序链表
题目类型
- 归并
题目链接
思路
先跳过吧 这题我不会做。。。
AC代码
LeetCode 160. 相交链表
题目类型
- 技巧题
题目链接
https://leetcode.cn/problems/intersection-of-two-linked-lists/
思路
AC代码
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* p = headA, *q = headB;
while (p != q)
{
if (p) p = p->next;
else p = headB;
if (q) q = q->next;
else q = headA;
}
return p;
}
};
LeetCode 203. 移除链表元素
题目类型
- 链表删除
题目链接
思路
思路简单 找到删除点 用链表删除就可以了
注意一下删除节点是head的情况 新创建一个虚拟头结点即可
AC代码
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
for (auto p = dummy; p;)
{
if (p->next && p->next->val == val)
p->next = p->next->next;
else
p = p->next;
}
return dummy->next;
}
};
LeetCode 206. 反转链表
题目类型
- 迭代
题目链接
思路
画图看比较简单
遍历链表，每次记录好cur结点的后继结点，再将cur指向cur的前驱结点，以此迭代下去
AC代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur)
{
ListNode* curNextTmp = cur->next;
cur->next = prev;
prev = cur, cur = curNextTmp;
}
return prev;
}
};
LeetCode 234. 回文链表
题目类型
- 反转链表
题目链接
思路
参考 LeetCode 206. 反转链表
- 链表的后半部分反转
- 使用双指针从链头和链尾往前判断
- 最后记得把链表恢复原状
时间复杂度O（n）
空间复杂度O（1）
AC代码
class Solution {
public:
bool isPalindrome(ListNode* head) {
int n = 0;
for (auto p = head; p; p = p->next) n ++;
if (n <= 1) return true;
int half = n / 2;
// 反转链表
ListNode* a = head;
for (int i = 0; i < n - half; i ++) a = a->next; // 将指针a指向翻转点
ListNode* b = a->next;
while (b)
{
ListNode* c = b->next;
b->next = a;
a = b, b = c;
}
// 判断是否是回文数
bool success = true;
ListNode* p = head, * q = a;
for (int i = 0; i < half; i ++) // 比较half次
{
if (p->val != q->val)
{
success = false;
break;
}
p = p->next, q = q->next;
}
// 恢复链表
ListNode* tail = a;
b = a->next;
for (int i = 0;i < half - 1; i ++)
{
ListNode* c = b->next;
b->next = a;
a = b, b = c;
}
tail->next = nullptr;
return success;
}
};
LeetCode 237. 删除链表中的节点
题目类型
- 删除
题目链接
思路
两行代码就可以
- 由于无法知道前驱结点 所以将下一个结点的值复制到当前节点
- 再删除下一个结点即可
AC代码
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};
LeetCode 876. 链表的中间结点
题目类型
- 快慢指针
题目链接
思路
比较简单 双指针问题 直接看代码就行
AC代码
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
LeetCode 328. 奇偶链表
题目类型
- 插入
- 合并
题目链接
思路
分为两个链表，最后拼接即可
AC代码
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
// 只有一个或两个元素直接返回原链表
if(!head || !(head->next)) return head;
// 定义奇数链表和偶数的链表的头结点和尾结点
ListNode* oh = head, * ot = oh;
ListNode* eh = head->next, * et = eh;
for (ListNode* p = head->next->next; p;)
{
ot = ot->next = p;
p = p->next;
if (p)
{
et = et->next = p;
p = p->next;
}
}
ot->next = eh;
et->next = nullptr;
return oh;
}
};
LeetCode 445. 两数相加 II
题目类型
- 高精度加法
题目链接
思路
由于这是链表，又为了人为习惯故意让结点从高位到低位，但不利于计算，所以这里需要反转链表
- 反转两个链表l1 l2
- 依次遍历两个链表，使用进位变量c，存储同一位的两个结点相加的结果
- 将结果取余放入结果链表中，进位变量c也要修改
AC代码
class Solution {
public:
ListNode* reverse(ListNode* head)
{
ListNode* prev = nullptr, *cur = head;
while (cur)
{
ListNode* cur_tmp_next = cur->next;
cur->next = prev;
prev = cur, cur = cur_tmp_next;
}
return prev;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1 = reverse(l1), l2 = reverse(l2);
// 存放结果
ListNode* res_dummy = new ListNode(-1);
int c = 0;
while (l1 || l2 || c)
{
if (l1) c += l1->val, l1 = l1->next;
if (l2) c += l2->val, l2 = l2->next;
ListNode* cur = new ListNode(c % 10);
c /= 10;
// 使用头插法
cur->next = res_dummy->next;
res_dummy->next = cur;
}
return res_dummy->next;
}
};
LeetCode 725. 分隔链表
题目类型
- 分段
题目链接
思路
将n个结点的链表分为k份， n % k == c
- 如果c == 0，说明刚刚好分，或者前面几个链表有结点，最后几个没有结点（即k> n的情况）
- 如果c != 0，则每个链表分配len = n/k结点外，前c个链表再分配一个结点
AC代码
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* head, int k) {
int n = 0;
for (auto p = head; p; p = p->next) n ++;
vector<ListNode*> res;
auto p = head;
for (int i = 0; i < k; i ++)
{
// 当前链表长度len
int len = n / k;
// 前n % k个链表多1个
if (i + 1 <= n % k) len ++;
res.push_back(p);
for (int j = 0; j < len - 1; j ++) p = p->next;
if (p)
{
auto q = p->next;
p->next = nullptr;
p = q;
}
}
return res;
}
};
##
题目类型
思路
AC代码
##【未完待更】
