25. K 个一组翻转链表 Reverse-nodes-in-k-group
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
相关题目： Leetcode 24. 两两交换链表中的节点 Swap Nodes In Pairs
示例 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) 额外内存空间的算法解决此问题吗？
代码1：
package main import "fmt" type ListNode struct { data int next *ListNode } func build(nums []int) *ListNode { if len(nums) == 0 { return nil } head := &ListNode{data: nums[0]} p := head for i := 1; i < len(nums); i++ { node := &ListNode{data: nums[i]} p.next = node p = p.next } return head } func (head *ListNode) travel() { for p := head; p != nil; p = p.next { fmt.Print(p.data) if p.next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func reverseKGroup(head *ListNode, k int) *ListNode { res := &ListNode{next: head} prev := res for head != nil { tail := prev for i := 0; i < k; i++ { tail = tail.next if tail == nil { return res.next } } node := tail.next start, end := reverse(head, tail) prev.next = start end.next = node prev = end head = node } return res.next } func reverse(start, end *ListNode) (*ListNode, *ListNode) { var prev *ListNode for cur := start; cur != end; { node := cur.next cur.next = prev prev = cur cur = node } end.next = prev return end, start } func main() { nums := []int{1, 2, 3, 4, 5} head := build(nums) head.travel() reverseKGroup(head, 2).travel() head = build(nums) reverseKGroup(head, 3).travel() head = build(nums) reverseKGroup(head, 4).travel() }
思路：使用res节点来指向原链表的头节点，每次将k个节点作为一个子链表，对子链表进行反转，并将原链表的前一个节点指向反转后的子链表的头节点，子链表的尾节点指向下一个子链表的头节点，以此类推，直到链表末尾。
代码2：
package main import "fmt" type ListNode struct { data int next *ListNode } func build(nums []int) *ListNode { if len(nums) == 0 { return nil } head := &ListNode{data: nums[0]} p := head for i := 1; i < len(nums); i++ { node := &ListNode{data: nums[i]} p.next = node p = p.next } return head } func (head *ListNode) travel() { for p := head; p != nil; p = p.next { fmt.Print(p.data) if p.next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func reverseKGroup(head *ListNode, k int) *ListNode { node := head for i := 0; i < k; i++ { if node == nil { return head } node = node.next } res := reverse(head, node) head.next = reverseKGroup(node, k) return res } func reverse(start, end *ListNode) *ListNode { cur, prev := start, end for cur != end { node := cur.next cur.next = prev prev = cur cur = node } return prev } func main() { nums := []int{1, 2, 3, 4, 5} head := build(nums) head.travel() reverseKGroup(head, 2).travel() head = build(nums) reverseKGroup(head, 3).travel() head = build(nums) reverseKGroup(head, 4).travel() }
输出：
1->2->3->4->5<nil>
2->1->4->3->5<nil>
3->2->1->4->5<nil>
4->3->2->1->5<nil>
26. 删除有序数组中的重复项 Remove-duplicates-from-sorted-array
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案 int k = removeDuplicates(nums); // 调用 assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }
如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [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]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 升序 排列
代码1：
package main import "fmt" func removeDuplicates(nums []int) int { if len(nums) == 0 { return 0 } slow := 0 for fast := 1; fast < len(nums); fast++ { if nums[fast] != nums[slow] { slow++ nums[slow] = nums[fast] } } return slow + 1 } func main() { nums := []int{1, 1, 2} res := removeDuplicates(nums) fmt.Println(res, nums[:res]) nums = []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4} res = removeDuplicates(nums) fmt.Println(res, nums[:res]) }
输出：
2 [1 2]
5 [0 1 2 3 4]
思路： 数组已是升序排列的，可以使用双指针法。定义一个慢指针和一个快指针，快指针用来遍历整个数组，慢指针用来指向不重复的元素。当快指针遇到不重复的元素时，将该元素赋值给慢指针指向的位置，然后慢指针向后移动一位。最后返回慢指针的位置即可。
代码2：
package main import "fmt" func removeDuplicates(nums []int) int { if len(nums) == 0 { return 0 } res, cur := 0, 0 for res < len(nums)-1 { for nums[cur] == nums[res] { cur++ if cur == len(nums) { return res + 1 } } nums[res+1] = nums[cur] res++ } return res + 1 } func main() { nums := []int{1, 1, 2} fmt.Println(removeDuplicates(nums)) nums = []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4} fmt.Println(removeDuplicates(nums)) }
27. 移除元素 Remove Element
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
代码：不考虑数组中超出新长度后面的元素
package main import "fmt" func removeElement(nums []int, val int) int { if len(nums) == 0 { return 0 } slow := 0 for fast := 0; fast < len(nums); fast++ { if nums[fast] != val { nums[slow] = nums[fast] slow++ } } return slow } func main() { nums := []int{3, 2, 2, 3} val := 3 res := removeElement(nums, val) fmt.Println(res, nums[:res]) fmt.Println(nums) nums = []int{0, 1, 2, 2, 3, 0, 4, 2} val = 2 res = removeElement(nums, val) fmt.Println(res, nums[:res]) fmt.Println(nums) }
输出：
2 [2 2]
[2 2 2 3]
5 [0 1 3 0 4]
[0 1 3 0 4 0 4 2]
思路：双指针法，定义一个快指针和一个慢指针，快指针遍历整个数组，当遇到不等于目标值的元素时，将该元素赋值给慢指针指向的位置，慢指针向后移动一位。最后返回慢指针的位置即可。由于元素的顺序可以改变，所以可以将目标值与最后一个元素交换位置，这样最后一个元素就变成了目标值，只需返回慢指针指向的位置即可。
代码2： 保留原数组的所有元素，即移除的val移到数组末尾
package main import "fmt" func removeElement(nums []int, val int) int { if len(nums) == 0 { return 0 } slow := 0 for fast := 0; fast < len(nums); fast++ { if nums[fast] != val { if fast != slow { nums[fast], nums[slow] = nums[slow], nums[fast] } slow++ } } return slow } func main() { nums := []int{3, 2, 2, 3} val := 3 res := removeElement(nums, val) fmt.Println(res, nums[:res]) fmt.Println(nums) nums = []int{0, 1, 2, 2, 3, 0, 4, 2} val = 2 res = removeElement(nums, val) fmt.Println(res, nums[:res]) fmt.Println(nums) }
输出：
2 [2 2]
[2 2 3 3]
5 [0 1 3 0 4]
[0 1 3 0 4 2 2 2]
