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_node
Java
/**
* 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]提示:
- 链表中的节点数目为
n
1 <= k <= n <= 5000
0 <= 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 prev
Java
/**
* 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 + 1
Java
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;
}
}
标签:24,链表,26,ListNode,nums,head,next,力扣,节点
From: https://blog.csdn.net/qq_52213943/article/details/136719923