【Leetcode -1171.从链表中删去总和值为零的连续节点 -1669.合并两个链表】

Leetcode -1171.从链表中删去总和值为零的连续节点

题目：给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。 删除完毕后，请你返回最终结果链表的头节点。 你可以返回任何满足题目要求的答案。 （注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1： 输入：head = [1, 2, -3, 3, 1] 输出：[3, 1] 提示：答案[1, 2, 1] 也是正确的。

示例 2： 输入：head = [1, 2, 3, -3, 4] 输出：[1, 2, 4]

示例 3： 输入：head = [1, 2, 3, -3, -2] 输出：[1]

提示： 给你的链表中可能有 1 到 1000 个节点。 对于链表中的每个节点，节点的值： - 1000 <= node.val <= 1000.

思路：思路相当是双指针，创建一个哨兵位dummy，prev从dummy开始，cur每次从prev的next 开始遍历，每次遍历中 cur 的 val 都进行累减，如果累减的结果有等于 0 的，就证明从 prev 的 next 到 cur 都是要删除的节点，所以直接将 prev 的 next 连到 cur 的 next ；

		struct ListNode* removeZeroSumSublists(struct ListNode* head)
		{
		    //创建哨兵位
		    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
		    dummy->next = head;
		
		    //prev从哨兵位开始，每次cur从prev的next开始遍历
		    //从 cur 的val开始累减，如果累减的结果为0，即直接让prev的next指向cur的next
		    struct ListNode* prev = dummy;
		    while (prev)
		    {
		        int sum = 0;
		        struct ListNode* cur = prev->next;
		        while (cur)
		        {
		            sum -= cur->val;
		            if (sum == 0)
		            {
		                prev->next = cur->next;
		            }
		            cur = cur->next;
		        }
		
		        //prev迭代
		        prev = prev->next;
		    }
		    return dummy->next;
		}

Leetcode -1669.合并两个链表

题目：给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。 请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。 请你返回结果链表的头指针。

示例 1： 输入：list1 = [0, 1, 2, 3, 4, 5], a = 3, b = 4, list2 = [1000000, 1000001, 1000002] 输出：[0, 1, 2, 1000000, 1000001, 1000002, 5] 解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

示例 2： 输入：list1 = [0, 1, 2, 3, 4, 5, 6], a = 2, b = 5, list2 = [1000000, 1000001, 1000002, 1000003, 1000004] 输出：[0, 1, 1000000, 1000001, 1000002, 1000003, 1000004, 6] 解释：上图中蓝色的边和节点为答案链表。

提示： 3 <= list1.length <= 10^4 1 <= a <= b < list1.length - 1 1 <= list2.length <= 10^4

思路：找到要删除的节点的前一个节点prev，以及要删除的最后一个节点cur，tail2为链表2的尾部节点；然后将 prev 的 next 接到链表2的头节点，链表2的尾节点接到 cur 的 next；

		struct ListNode* mergeInBetween(struct ListNode* list1, int a, int b, struct ListNode* list2)
		{
		    struct ListNode* prev = list1, * cur = list1, * tail2 = list2;
		
		    //prev为需要删除的第一个节点的前一个节点
		    while (--a)
		        prev = prev->next;
		
		    //cur为需要删除的最后一个节点
		    while (b--)
		        cur = cur->next;
		
		    //tail2为链表2的尾
		    while (tail2->next)
		        tail2 = tail2->next;
		
		    //将 prev 的next接到链表2；链表2的尾接到cur的next
		    prev->next = list2;
		    tail2->next = cur->next;
		
		    return list1;
		}