您现在的位置是:首页 >技术教程 >【Leetcode -147.对链表进行插入排序 -237.删除链表中的节点】网站首页技术教程

【Leetcode -147.对链表进行插入排序 -237.删除链表中的节点】

YoungMLet 2023-07-01 04:00:02
简介【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;
		}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。