Leetcodes刷题之删除链表的倒数N个结点和删除链表的中间的结点

吾心信其可行，则移山填海之难，终有成功之日。                           --孙中山
目录

🍉一.删除链表的倒数N个结点

🌻1.双指针

🍁2.求链表的长度

🌸二.删除链表的中间的结点

---

🍉一.删除链表的倒数N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

做题链接

🌻1.双指针

这题我们同样使用双指针的方法，我们先定义一个fast指针和slow指针，它们都指向head。

第一步：先判断fast为不为空，不为空，n就减1，fast再走一步。依次循环，直到n减到0，即退出循环。
第二步：然后slow指针和fast再同时移动，直到fast走到链表的尾，此时slow即要找到的指针，即要删除的指针。

但是这样做只是找到你要删除的结点，这题你不仅要找到倒数的N个结点，还要把这个结点的前后结点给链接起来。 

大体方法还是这个方法，但是可能fast和slow初始指向链表的位置不同，这题我们创建一个哨兵位的头结点来实现，开始fast和slow指针指向phead，我们还是通过画图来理解。

直接上代码： 

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));phead->next = head;struct ListNode* fast = phead, * slow = phead;while (n--){fast = fast->next;//fast先走}while (fast->next){fast = fast->next;//此时两个指针遍历链表slow = slow->next;}slow->next = slow->next->next;struct ListNode* next = phead->next;//保存哨兵位的下一个结点free(phead);//释放哨兵结点return next;
}

这题的难点就是该如何把要删除结点的前后结点链接起来，这就需要仔细的把fast和slow初始的位置给放对才行。

🍁2.求链表的长度

我们先创建一个函数遍历链表，把链表的长度len给算出来。也是和上面一样，我们还是创建一个哨兵位的头结点phead，然后使用一个cur指针指向phead，然后cur走len-n个结点，就找到了要删除结点的前一个结点，然后cur->next=cur->next->next即可。

int longlinked(struct ListNode*head)
{int len=0;while(head){len++;head=head->next;}return len;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{int len=longlinked(head);struct ListNode*phead=(struct ListNode*)malloc(sizeof(struct ListNode));phead->next=head;struct ListNode*cur=phead;int i=0;while(i<len-n){cur=cur->next;i++;}cur->next=cur->next->next;struct ListNode*second=phead->next;free(phead);phead=NULL;return second;
}

🌸二.删除链表的中间的结点

给你一个链表的头节点head 。删除 链表的中间节点 ，并返回修改后的链表的头节点head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

• 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

示例 1：

输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。 

示例 2： 

 

输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。

 示例 3：

输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

做题链接

之前我们就写了找中间结点的链表题，但是上次那个只是找到中间结点即可，使用快慢指针来实现，这题就是那个题的变形，找到中间结点给删除掉，然后把中间结点的前后给链接起来，我们同样是创建一个哨兵位的结点，然后使用快慢指针来实现。fast指针指向head，而slow指针指向phead。

当fast指向链表的尾时，slow这时指向中间结点的前一个，然后链接起来就是。

struct ListNode* deleteMiddle(struct ListNode* head){if(head->next==NULL)return NULL;struct ListNode*phead=(struct ListNode*)malloc(sizeof(struct ListNode));phead->next=head;struct ListNode*fast=head,*slow=phead;  while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}slow->next=slow->next->next;struct ListNode*next=phead->next;free(phead);phead=NULL;return next;
}