删除链表的中间节点
问题重述：
给你一个链表的头节点 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 后剩下的唯一一个节点。
问题分析：
这道题让我们删除链表的中间节点，我们很快可以联想到使用快慢指针，快慢指针在对于删除链表中的某个结点的效果非常好，删除中间节点，我们可以使得慢指针每次移动1，快指针每次移动2，当快指针移动到末尾的时候，此时的慢指针指向的就是我们要删除的结点（ 为了便于删除结点，我们可以使用dummy结点来简便操作）
解法：
快慢指针
解题：
代码：
public ListNode deleteMiddle(ListNode head) {
if(head == null || head.next == null) {
// 当链表为空或者链表长度为1，没有中间节点，直接返回head
return null;
}else if(head.next.next == null) {
// 当链表的长度大于1，等于2的时候，删除头节点
head.next = null;
return head;
}
// 当链表的长度大于2的时候，使用快慢指针删除结点（快指针速度为2，慢指针速度为1，即可实现找到中间节点）
ListNode fast = head;
ListNode slow = head;
ListNode pri = new ListNode(-1);
pri.next = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
pri = pri.next;
}
if(fast.next == null){
pri.next = pri.next.next;
}else if(fast.next.next == null){
slow.next = slow.next.next;
}
return head;
}
代码解析：
当链表长度为空或者为1的时候，没有中间节点，直接返回null（只有一个节点的时候此时的结点就是中间结点），当长度为2的时候，删除后面的结点，直接将head.next指向空然后返回head即可。
当链表长度大于2的时候，此时我们就需要使用快慢指针来删除节点，为了便于删除，我们添加了pri结点用于记录要删除的结点的上一个结点（ 其实我们可以使用dummy结点来直接简化操作，此时只需要创建一个连接到head的结点dummy，然后使得slow指针指向dummy即可），我们慢指针每走一步，快指针就要走两步，当快指针不能继续往后走的时候，此时的pri指向的就是要删除的节点的上一个结点。
总结：
快慢指针常用于删除链表中的某个结点
模板：
//创建一个dummy结点，该节点的下一个结点为head
Node dummy = new Node(0);
dummy.next = head;
Node fast = head;
Node slow = dummy;//为了得到所需节点的上一个结点
while(循环条件){
//更新快慢指针
}
// 此时的slow指针对应的就是我们要找的结点，对该节点进行操作
Original: https://www.cnblogs.com/foldn/p/15918703.html
Author: foldn
Title: 删除链表的中间节点
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/579766/
转载文章受原作者版权保护。转载请注明原作者出处！