删除链表的中间节点

问题重述：

给你一个链表的头节点 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指针对应的就是我们要找的结点，对该节点进行操作