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 ）进⾏翻转，

1. 先分组，⽤⼀个 count 变量记录当前节点的个数
2. ⽤⼀个 start 变量记录当前分组的起始节点位置的前⼀个节点
3. ⽤⼀个 end 变量记录要翻转的最后⼀个节点位置
4. 翻转⼀组（ k个nodes ）即 (start, end) - start and end exclusively 。
5. 翻转后， start 指向翻转后链表, 区间 （start，end） 中的最后⼀个节点, 返回 start 节 点。
6. 如果不需要翻转， end 就往后移动⼀个（ end=end.next )，每⼀次移动，都要 count+1 .

如图所示 步骤 4 和 5： 翻转区间链表区间 （start， end）

复杂度分析

时间复杂度: O(n) - n is number of Linked List 空间复杂度: O(1) 关键点分析

1. 创建⼀个 dummy node
2. 对链表以 k 为单位进⾏分组，记录每⼀组的起始和最后节点位置
3. 对每⼀组进⾏翻转，更换起始和最后的位置
4. 返回 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 个为⼀组进⾏翻转类似，可以进⾏预处理：

1. 翻转链表
2. 对翻转后的链表进⾏从前往后以 k 为⼀组翻转。
3. 翻转步骤 2 中得到的链表。 例⼦： 1->2->3->4->5->6->7->8, k = 3
4. 翻转链表得到： 8->7->6->5->4->3->2->1
5. 以 k 为⼀组翻转： 6->7->8->3->4->5->2->1
6. 翻转步骤#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 < len; i++) { print(nums[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 < size; fastP++) {
    if (nums[fastP] !== nums[slowP]) {
      slowP++;
      nums[slowP] = nums[fastP];
    }
  }
  return slowP + 1;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

7. 两数相除

题⽬描述

给定两个整数，被除数 dividend 和除数 divisor。

将两数相除，要求不使⽤乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其⼩数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1: 输⼊: dividend = 10, divisor = 3

输出: 3

解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输⼊: dividend = 7, divisor = -3

输出: -2

解释: 7/-3 = truncate(-2.33333..) = -2

提示： 被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结 果溢出，则返回 231 − 1。

前置知识

⼆分法

思路

符合直觉的做法是，减数⼀次⼀次减去被减数，不断更新差，直到差⼩于 0，我们减了多少次，结果就是多少。

let acc = divisor;
let count = 0;
while (dividend - acc >= 0) {
 acc += divisor;
 count++;
}
return count;

这种做法简单直观，但是性能却⽐较差. 下⾯来介绍⼀种性能更好的⽅法。

我们可以使⽤⼆分法来解决，性能有很⼤的提升。

代码

/*
 * @lc app=leetcode id=29 lang=javascript
 *
 * [29] Divide Two Integers
 */
/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (dividend, divisor) {
  if (divisor === 1) return dividend;
  // 这种⽅法很巧妙，即符号相同则为正，不同则为负
  const isNegative = dividend > 0 !== divisor > 0;
  const MAX_INTERGER = Math.pow(2, 31);
  const res = helper(Math.abs(dividend), Math.abs(divisor));
  // overflow
  if (res > MAX_INTERGER - 1 || res < -1 * MAX_INTERGER) {
    return MAX_INTERGER - 1;
  }
  return isNegative ? -1 * res : res;
};
function helper(dividend, divisor) {
  // ⼆分法
  if (dividend <= 0) return 0;
  if (dividend < divisor) return 0;
  if (divisor === 1) return dividend;
  let acc = 2 * divisor;
  let count = 1;
  while (dividend - acc > 0) {
    acc += acc;
    count += count;
  }
  // 直接使⽤位移运算，⽐如acc >> 1会有问题
  const last = dividend - Math.floor(acc / 2);
  return count + helper(last, divisor);
}

复杂度分析

时间复杂度：logN

空间复杂度：O(1)

8. 下⼀个排列

题⽬描述

实现获取下⼀个排列的函数，算法需要将给定数字序列重新排列成字典序中下⼀个更⼤的排列。

如果不存在下⼀个更⼤的排列，则将数字重新排列成最⼩的排列（即升序排列）。

必须原地修改，只允许使⽤额外常数空间。 以下是⼀些例⼦，输⼊位于左侧列，其相应输出位于右侧列。

1,2,3 -> 1,3,2

3,2,1 -> 1,2,3

1,1,5 -> 1,5,1

前置知识

回溯法

思路

符合直觉的⽅法是按顺序求出所有的排列，如果当前排列等于 nums，那么我直接取下⼀个但是

这种做法不符合 constant space 要求（题⽬要求直接修改原数组）,时间复杂度也太⾼，为 O(n!),肯定不是合适的解。 我们也可以以回溯的⻆度来思考这个问题，即从后往前思考。 让我们先回溯⼀次，即思考最后⼀个数字是如何被添加的。