您现在的位置是:首页 >技术教程 >【Leetcode -147.对链表进行插入排序 -237.删除链表中的节点】网站首页技术教程
【Leetcode -147.对链表进行插入排序 -237.删除链表中的节点】
Leetcode -147.对链表进行插入排序
题目: 给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。
插入排序 算法的步骤 :
插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
重复直到所有输入数据插入完为止。
示例 1:
输入: head = [4, 2, 1, 3]
输出 : [1, 2, 3, 4]
示例 2:
输入: head = [-1, 5, 3, 4, 0]
输出 : [-1, 0, 3, 4, 5]
我们的思路是,使用两个指针sorttail和cur比较相邻的两个元素,cur为sorttail的next,sorttail走到最后是链表的尾,所以应该是val最大的节点,所以sorttail的后面如果还有节点,要么sorttail当前还不是val最大的节点,这时候就更新sorttail即可;要么就说明还没排序好,这时候就定义一个指针prev,prev从哨兵位开始,prev找到比cur的val大的节点的上一个节点,改变它们的相对位置,还要保持原链表的相对位置不变;
假设链表的值为:5->3->1->4->2->NULL
第一次迭代:
第一次迭代排序好的链表:
第二次迭代:
第二次迭代排序好的链表:
第三次迭代:
第三次迭代排序好的链表:
第四次迭代:
第四次迭代排序好的链表,此时cur为空,循环结束:
代码和注释:
struct ListNode* insertionSortList(struct ListNode* head)
{
//创建一个哨兵位
struct ListNode* dummy = malloc(sizeof(struct ListNode));
dummy->next = head;
//cur
struct ListNode* cur = head->next;
struct ListNode* sorttail = head;
while (cur)
{
//比较相邻的两个节点
//sorttail为排序的最后一个节点,即为最大的节点,所以只要sorttail后面还有节点,
//要么就要更新sorttail,要么就要改变节点的相对位置
//如果有比sorttail的val大或者等于的值,就更新sorttail,
//往后走就行,因为sorttail的next就是cur
if (sorttail->val <= cur->val)
{
sorttail = sorttail->next;
}
//当sorttail->val比cur->val大,说明cur应该出现在sorttail的前面,所以需要改变节点的相对位置
//至于需要与哪个节点交换,就要重新定义一个指针prev
//prev从哨兵位开始走,直到prev->next->val 大于 cur->val
//就将cur更新到前面,位置在prev的next,再保持原来链表的相对位置不变
else
{
struct ListNode* prev = dummy;
while (prev->next->val <= cur->val)
{
prev = prev->next;
}
sorttail->next = cur->next;
cur->next = prev->next;
prev->next = cur;
}
//因为sorttail到最后是链表中的最后一个节点,所以cur应该迭代sorttail往后走,直到空就结束,不为空就说明还没排序好
cur = sorttail->next;
}
//返回哨兵位的next即可
return dummy->next;
}
Leetcode - 237.删除链表中的节点
有一个单链表的 head,我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的,并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意,删除节点并不是指从内存中删除它。这里的意思是:
给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。
示例 1:
输入:head = [4, 5, 1, 9], node = 5
输出:[4, 1, 9]
解释:指定链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9
示例 2:
输入:head = [4, 5, 1, 9], node = 1
输出:[4, 5, 9]
解释:指定链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9
我们的思路是,直接改变节点的值为下一个节点的值,再更新当前节点的next即可;
//改变当前节点的值为下一个节点的值
//再更新当前节点的next
void deleteNode(struct ListNode* node)
{
node->val = node->next->val;
node->next = node->next->next;
}