5. K 个⼀组翻转链表
题⽬描述
给你⼀个链表，每 k 个节点⼀组进⾏翻转，请你返回翻转后的链表。
k 是⼀个正整数，它的值⼩于或等于链表的⻓度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
你的算法只能使⽤常数的额外空间。
你不能只是单纯的改变节点内部的值，⽽是需要实际进⾏节点交换。
思服务器托管网路
题意是以 k 个 nodes 为⼀组进⾏翻转，返回翻转后的 linked list .
从左往右扫描⼀遍 linked list ，扫描过程中，以 k 为单位把数组分成若⼲段，对每⼀段进⾏
翻转。给定⾸尾 nodes，如何对链表进⾏翻转。
链表的翻转过程，初始化⼀个为 null 的 previous node（prev） ，然后遍历链表的同时，当
前 node （curr） 的下⼀个（next）指向前⼀个 node（prev） ，
在改变当前 node 的指向之前，⽤⼀个临时变量记录当前 node 的下⼀个 node（curr.next) . 即
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
举例如图：翻转整个链表 1->2->3->4->null -> 4->3->2->1->null
这⾥是对每⼀组（ k个nodes ）进⾏翻转，
- 先分组，⽤⼀个 count 变量记录当前节点的个数
- ⽤⼀个 start 变量记录当前分组的起始节点位置的前⼀个节点
- ⽤⼀个 end 变量记录要翻转的最后⼀个节点位置
- 翻转⼀组（ k个nodes ）即 (start, end) – start and end exclusively 。
- 翻转后， start 指向翻转后链表, 区间 （start，end） 中的最后⼀个节点, 返回 start 节
点。 - 如果不需要翻转， end 就往后移动⼀个（ end=end.next )，每⼀次移动，都要 count+1 .
如图所示 步骤 4 和 5： 翻转区间链表区间 （start， end）
复杂度分析
时间复杂度: O(n) – n is number of Linked List
空间复杂度: O(1)
关键点分析
- 创建⼀个 dummy node
- 对链表以 k 为单位进⾏分组，记录每⼀组的起始和最后节点位置
- 对每⼀组进⾏翻转，更换起始和最后的位置
- 返回 dummy.next .
代码
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function (head, k) {
// 标兵
let dummy = new ListNode();
dummy.next = head;
let [start, end] = [dummy, dummy.next];
let count = 0;
while (end) {
count++;
if (count % k === 0) {
start = reverseList(start, end.next);
end = start.next;
} else {
end = end.next;
}
}
return dummy.next;
// 翻转stat -> end的链表
function reverseList(start, end) {
let [pre, cur] = [start, start.next];
const first = cur;
while (cur !== end) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
start.next = pre;
first.next = cur;
return first;
}
};
参考（References)
Leetcode Discussion (yellowstone)
扩展 1
要求从后往前以 k 个为⼀组进⾏翻转。(字节跳动（ByteDance）⾯试题)
例⼦， 1->2->3->4->5->6->7->8, k = 3 ,
从后往前以 k=3 为⼀组，
6->7->8 为⼀组翻转为 8->7->6 ，
3->4->5 为⼀组翻转为 5->4->3 .
1->2 只有 2 个 nodes 少于 k=3 个，不翻转。
最后返回： 1->2->5->4->3->8->7->6
这⾥的思路跟从前往后以 k 个为⼀组进⾏翻转类似，可以进⾏预处理：
- 翻转链表
- 对翻转后的链表进⾏从前往后以 k 为⼀组翻转。
- 翻转步骤 2 中得到的链表。
例⼦： 1->2->3->4->5->6->7->8, k = 3 - 翻转链表得到： 8->7->6->5->4->3->2->1
- 以 k 为⼀组翻转： 6->7->8->3->4->5->2->1
- 翻转步骤#2 链表： 1->2->5->4->3->8->7->6
扩展 2
如果这道题你按照 92.reverse-linked-list-ii 提到的 p1, p2, p3, p4 （四点法） 的思路来思考
的话会很清晰。
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
6.删除排序数组中的重复项
题⽬描述
给定⼀个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现⼀次，返回移除
后数组的新⻓度。
不要使⽤额外的数组空间，你必须在 原地 修改输⼊数组 并在使⽤ O(1) 额外空间的条件下完成。
示例
1:
给定数组 nums = [1,1,2],
函数应该返回新的⻓度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新⻓度后⾯的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的⻓度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新⻓度后⾯的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输⼊数组是以「引⽤」⽅式传递的，这意味着在函数⾥修改输⼊数组对于调⽤者是可
⻅的。
你可以想象内部操作如下:
// nums 是以“引⽤”⽅式传递的。也就是说，不对实参做任何拷⻉
int len = removeDuplicates(nums);
// 在函数⾥修改输⼊数组对于调⽤者是可⻅的。
// 根据你的函数返回的⻓度, 它会打印出数组中该⻓度范围内的所有元素。
for (int i = 0; i
前置知识
数组
双指针
思路
使⽤快慢指针来记录遍历的坐标。
- 开始时这两个指针都指向第⼀个数字
- 如果两个指针指的数字相同，则快指针向前⾛⼀步
- 如果不同，则两个指针都向前⾛⼀步
- 当快指针⾛完整个数组后，慢指针当前的坐标加 1 就是数组中不同数字的个数
实际上这就是双指针中的快慢指针。在这⾥快指针是读指针， 慢指针是写指针。从读写指针考虑， 我觉得更符合本质。
关键点解析
双指针
这道题如果不要求，O(n) 的时间复杂度， O(1) 的空间复杂度的话，会很简单。
但是这道题是要求的，这种题的思路⼀般都是采⽤双指针
如果是数据是⽆序的，就不可以⽤这种⽅式了，从这⾥也可以看出排序在算法中的基础性
和重要性。
注意 nums 为空时的边界条件。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums) {
const size = nums.length;
if (size == 0) return 0;
let slowP = 0;
for (let fastP = 0; fastP 复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: jenkins的安装和配置(flask结合jenkins半自动化部署流程)
jenkins在虚拟机中安装 1.1 背景介绍 Jenkins 是一款流行的开源持续集成（Continuous Integration）工具，广泛用于项目开发，具有自动化构建、测试和部署等功能。 Jenkins官网： http://jenkins-ci.org…
