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 <= 100
• 0 <= 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]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= 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]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= 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;}
};