Leetcode

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;
		}