leetcode-链表篇3
leetcode-61
给你一个链表的头节点
head，旋转链表，将链表每个节点向右移动k个位置。示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]示例 2：
输入：head = [0,1,2], k = 4 输出：[2,0,1]提示：
- 链表中节点的数目在范围
[0, 500]内-100 <= Node.val <= 1000 <= k <= 2 * 109
思路：看图片可以发现，这个题目本质上，是把链表分成两部分，交换前后两部分的顺序
所以重点在于找到分裂点，以及拼接
/*** 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* rotateRight(ListNode* head, int k) {if(!head || !head->next || k == 0) {return head;}auto tmp = head;int count = 0;auto tail = head;while(tmp) {tail = tmp;tmp = tmp->next;++count;}tmp = head;k %= count;if(k == 0) {return head;}k = count - k;while(--k && tmp) {tmp = tmp->next;}auto new_head = tmp->next;tmp->next = nullptr;tail->next = head;return new_head;}
};leetcode-206
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]提示：
- 链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
思路：递归法比较简单，还是我们的老模板
void circle(ListNode *head) {if(...) {return } //边界条件auto res = circle(head->next);//other code//return
}迭代法也是一器破万法。
关于链表反转的题目，都分成两部分，pre和curr
pre就是已经处理好的部分的尾节点， curr就是你要处理的部分的头节点
所以伪代码如下
//关于翻转链表相关的题目
while(xxx) {process(curr); //实现翻转的逻辑pre = curr; //当前部分已经处过，所以pre变成currcurr = curr->next; //curr->next还没处理过，所以curr指向自己的next继续处理
}/*** 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* reverseList(ListNode* head) {if(!head || !head->next) {return head;}// auto next = reverseList(head->next);// auto tmp = head->next;// head->next = nullptr;// tmp->next = head;// return next;auto pre = head;pre = nullptr;while(head) {auto next = head->next;head->next = nullptr;head->next = pre;pre = head;head = next;}return pre;}
};leetcode-92
给你单链表的头指针
head和两个整数left和right，其中left <= right。请你反转从位置left到位置right的链表节点，返回 反转后的链表 。示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]提示：
- 链表中节点数目为
n1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n进阶： 你可以使用一趟扫描完成反转吗？
思路，和上题一样，不过是对翻转的区间有限制了。
加上前缀节点pre，找到要翻转的区间的头尾节点，将之翻转后。拼接回原来的链表
/*** 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* reverseBetween(ListNode* head, int left, int right) {if(!head || !head->next) {return head;}auto tmp = new ListNode(-1);tmp->next = head;auto pre = tmp;int count = left;while(--count) {tmp = tmp->next;}auto curr = tmp->next;for(int i=0; i<right-left; i++) {auto tail = curr->next->next;auto next = curr->next;curr->next = tail;auto new_tail = tmp->next;tmp->next = next;next->next = new_tail;}return pre->next;}
};leetcode-24
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]示例 2：
输入：head = [] 输出：[]示例 3：
输入：head = [1] 输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内0 <= Node.val <= 100
思路：还记得我们一器破万法的迭代法模板吗，直接套用就可以
/*** 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) {if(!head || !head->next) {return head;}auto pre = new ListNode(-1);pre->next = head;auto curr = head;auto tmp = pre;while(curr && curr->next) {auto tail = curr->next->next;auto next = curr->next;curr->next = tail;auto new_tail = tmp->next;next->next = new_tail;tmp->next = next;tmp = curr;curr = curr->next;}return pre->next;}
};leetcode-25
给你链表的头节点
head，每k个节点一组进行翻转，请你返回修改后的链表。
k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]示例 2：
输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]提示：
- 链表中的节点数目为
n1 <= k <= n <= 50000 <= Node.val <= 1000进阶：你可以设计一个只用
O(1)额外内存空间的算法解决此问题吗？
思路：做了以上几道题目，总结了自己的一器破万法模板之后，发现这个题竟然这么简单
以前被自己视为面试杀手的接雨水，k个一组翻转链表也变得简单起来
这题和上一题的唯一不同就在于，需要遍历一遍算出链表的长度，避免越界
/*** 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) {auto tmp = head;int count=0;while(tmp) {++count;tmp = tmp->next;}if(!head || !head->next || k>count || k<=1) {return head;}auto pre = new ListNode(-1);pre->next = head;tmp = pre;auto curr = head; for(int i=0; i<count/k; i++) {for(int j=1; j<k; j++) {auto tail = curr->next->next;auto next = curr->next;curr->next = tail;auto new_tail = tmp->next;next->next = new_tail;tmp->next = next;}tmp = curr;curr = curr->next;}return pre->next;}
};