龙岗网站设计效果,手机网站打开微信支付功能,wordpress single,莱芜金点子最新招聘平台24. 两两交换链表中的节点#xff0c;25. K 个一组翻转链表#xff0c;26. 删除有序数组中的重复项#xff0c;每题做详细思路梳理#xff0c;配套PythonJava双语代码#xff0c; 2024.03.14 可通过leetcode所有测试用例。
目录
24. 两两交换链表中的节点
解题思路… 24. 两两交换链表中的节点25. K 个一组翻转链表26. 删除有序数组中的重复项每题做详细思路梳理配套PythonJava双语代码 2024.03.14 可通过leetcode所有测试用例。
目录
24. 两两交换链表中的节点
解题思路
递归思路
迭代思路
完整代码
Python
Java
25. K 个一组翻转链表
解题思路
完整代码
Python
Java
26. 删除有序数组中的重复项
解题思路
完整代码
Python
Java 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, val0, nextNone):
# self.val val
# self.next next
class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:if not head or not head.next:return headnext_node head.nexthead.next self.swapPairs(next_node.next)next_node.next headreturn 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]提示 链表中的节点数目为 n1 k n 50000 Node.val 1000 进阶你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗 解题思路
找到k个一组的链表节点 遍历链表每次移动k步来定位到每个组的最后一个节点。如果剩余节点不足k个则保持这部分不变。反转每组节点 对于每个分组进行链表反转操作。这里需要注意的是反转操作不仅需要反转内部的节点还要连接好每组的头尾。连接各组 反转完一组后需要将反转后的子链表重新连接起来。这涉及到更新前一组的尾节点指向当前组反转后的头节点。
完整代码
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]:# 创建一个哑节点便于处理头节点前的操作dummy ListNode(0)dummy.next headpre, end dummy, dummywhile end.next:# 尝试移动end指针找到当前组的最后一个节点for _ in range(k):end end.nextif 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 startend prereturn dummy.nextdef reverse(self, head: ListNode) - ListNode:# 辅助函数翻转链表prev Nonewhile 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 0i 0for j in range(1, len(nums)):if nums[j] ! nums[i]:i 1nums[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;}
}
