240425 leetcode exercises
240425 leetcode exercises
@jarringslee
文章目录
147. 对链表进行插入排序
给定单个链表的头
head，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。插入排序 算法的步骤:
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1：
输入: head = [4,2,1,3] 输出: [1,2,3,4]示例 2：
输入: head = [-1,5,3,4,0] 输出: [-1,0,3,4,5]
🔁插入排序
在数组中，插入和移动元素可能涉及大量的数据移动，而在链表中，只需调整指针即可完成插入操作，因此插入排序在链表中更为高效。
我们将链表分为两个部分：已排序部分和未排序部分。初始时，已排序部分只包含链表的第一个节点，其余节点组成未排序部分。我们逐个从未排序部分取出节点，插入到已排序部分的正确位置，直到未排序部分为空。
为了简化插入操作，特别是在头部插入的情况，我们引入一个虚拟头节点。这个虚拟头节点的值可以设为任意值（如0），其next指针指向原链表的头节点。
struct ListNode *insertionSortList(struct ListNode *head) {
if (head == NULL) return head;
// 创建虚拟头节点
struct ListNode *newHead = malloc(sizeof(struct ListNode));
newHead->val = 0;
newHead->next = head;
struct ListNode *last = head; // 已排序部分的最后一个节点
struct ListNode *curr = head->next; // 当前待插入的节点
while (curr != NULL) {
if (last->val <= curr->val) {
// 当前节点已经在正确位置，无需移动
last = last->next;
} else {
// 找到插入位置
struct ListNode *prev = newHead;
while (prev->next->val <= curr->val) {
prev = prev->next;
}
// 插入当前节点到正确位置
last->next = curr->next;
curr->next = prev->next;
prev->next = curr;
}
curr = last->next;
}
return newHead->next;
}
- 插入排序在链表中实现相对简单，特别适用于小规模数据或部分有序的数据。
- 通过引入虚拟头节点，可以简化插入操作，避免处理特殊情况。
- 虽然时间复杂度较高，但在特定场景下，插入排序仍然是一个不错的选择。
1721. 交换链表中的节点
交换 链表正数第
k个节点和倒数第k个节点的值后，返回链表的头节点（链表 从 1 开始索引）。示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[1,4,3,2,5]示例 2：
输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5 输出：[7,9,6,6,8,7,3,0,9,5]示例 3：
输入：head = [1], k = 1 输出：[1]示例 4：
输入：head = [1,2], k = 1 输出：[2,1]示例 5：
输入：head = [1,2,3], k = 2 输出：[1,2,3]
🔁双指针
首先我们定位整数第k个结点。使用一个指针 fast 从头开始，向前移动 k-1 次，fast 此时指向第 k 个节点，并将该节点保存为 tar1。继续使用 fast 指针向前移动，直到到达链表末尾。同时，使用另一个指针 tar2 从头开始来定位倒数第k个结点，每次 fast 向前移动时，tar2 也向前移动。当 fast 到达末尾时，tar2 指向的就是倒数第 k 个节点。
交换 tar1 和 tar2 的 val 值。
为什么使用 --k 而不是 k-- ？？？
使用 while (--k) 而不是 while (k--) 是为了确保指针 fast 向前移动 k-1 次，从而指向第 k 个节点。
--k是前缀递减，表示在使用k之前先将其减 1。k--是后缀递减，表示在使用k之后再将其减 1。
如果使用 k--，则循环会执行 k 次，fast 最终会指向第 k+1 个节点，导致错误。
struct ListNode* swapNodes(struct ListNode* head, int k) {
struct ListNode *tar1, *tar2;
struct ListNode *fast = head;
tar2 = head;
// 移动 fast 指针 k-1 次，fast 指向第 k 个节点
while (--k) {
fast = fast->next;
}
tar1 = fast;
// 继续移动 fast 到链表末尾，同时移动 tar2
while (fast->next) {
fast = fast->next;
tar2 = tar2->next;
}
// 交换 tar1 和 tar2 的值
int temp = tar1->val;
tar1->val = tar2->val;
tar2->val = temp;
return head;
}
原文地址：https://blog.csdn.net/2401_87805056/article/details/147523838
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！