24. 两两交换链表中的节点，25. K 个一组翻转链表，26. 删除有序数组中的重复项，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.14 可通过leetcode所有测试用例。
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]示例 2：
输入：head = [] 输出：[]示例 3：
输入：head = [1] 输出：[1]
解题思路
两种方式。
递归思路
- 终止条件：当前节点为空或者下一个节点为空，说明没有更多的节点需要交换，直接返回当前节点。
- 递归单元内需要做什么：交换当前节点和下一个节点的位置。
- 如何进入下一层递归：将当前节点的指针指向递归后返回的头节点。
迭代思路
- 创建一个哑节点（dummy node），它的下一个节点指向头节点。
- 初始化两个指针
prev和curr，其中prev指向哑节点，curr指向头节点。 - 遍历链表，当
curr及其下一个节点不为空时，执行以下操作： a. 记录curr的下一个节点为next。 b. 使curr的下一个节点指向next的下一个节点。 c. 使next的下一个节点指向prev的下一个节点。 d. 使prev的下一个节点指向next。 e. 更新prev和curr指针，准备下一对节点的交换。
完整代码
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
next_node = head.next
head.next = self.swapPairs(next_node.next)
next_node.next = head
return next_nodeJava
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while (head != null && head.next != null) {
ListNode first = head;
ListNode second = head.next;
prev.next = second;
first.next = second.next;
second.next = first;
prev = first;
head = first.next;
}
return dummy.next;
}
}
25. K 个一组翻转链表
给你链表的头节点
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个一组的链表节点： 遍历链表，每次移动k步来定位到每个组的最后一个节点。如果剩余节点不足k个，则保持这部分不变。
- 反转每组节点： 对于每个分组，进行链表反转操作。这里需要注意的是，反转操作不仅需要反转内部的节点，还要连接好每组的头尾。
- 连接各组： 反转完一组后，需要将反转后的子链表重新连接起来。这涉及到更新前一组的尾节点指向当前组反转后的头节点。
完整代码
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 创建一个哑节点，便于处理头节点前的操作
dummy = ListNode(0)
dummy.next = head
pre, end = dummy, dummy
while end.next:
# 尝试移动end指针，找到当前组的最后一个节点
for _ in range(k):
end = end.next
if not end: # 如果节点数不足k个，不进行翻转
return dummy.next
# 记录下一组的起始节点
start, next = pre.next, end.next
# 断开当前组与下一组的连接，以便单独翻转当前组
end.next = None
# 翻转当前组，并将翻转后的子链表接回原链表
pre.next = self.reverse(start)
# 重新连接翻转后的子链表与下一组的起始节点
start.next = next
# 移动pre和end指针到下一组的起始位置
pre = start
end = pre
return dummy.next
def reverse(self, head: ListNode) -> ListNode:
# 辅助函数：翻转链表
prev = None
while head:
next_temp = head.next # 临时存储下一个节点
head.next = prev # 将当前节点指向前一个节点，实现翻转
prev = head # 移动prev指针
head = next_temp # 移动head指针
return prevJava
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) end = end.next;
if (end == null) break;
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = pre;
}
return dummy.next;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
26. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
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 。不需要考虑数组中超出新长度后面的元素。
解题思路
要解决这个问题，我们可以采用双指针技术。思路是用两个指针i和j遍历数组，i是慢指针，j是快指针。当nums[i]和nums[j]相等时，增加j以跳过重复项。当遇到nums[i]和nums[j]不相等时，则将nums[j]的值复制到nums[i + 1]，然后递增i，接着递增j。重复这一过程，直到j遍历完整个数组。数组的前i + 1个元素就是不含重复元素的数组。最后返回的i + 1就是数组中不同元素的个数。
完整代码
Python
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1Java
public class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
}
