删除链表的中间节点

题目链接

删除链表的中间节点

题目描述

注意点

• 链表中节点的数目在范围 [1, 100000] 内

解答思路

• 快慢指针找到链表中间节点的前一个节点，慢指针每次跳一格，快指针每次跳两格，当快指针跳到链表末尾时，此时慢指针刚好到链表的中间节点。为了方便找到中间节点的前一个节点，慢指针的初始位置在链表的第一个节点，快指针的初始位置设置在链表的第二个节点

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        // 找到中间节点的前一个节点
        ListNode slow = head;
        ListNode quick = head.next;
        while (quick.next != null && quick.next.next != null) {
            slow = slow.next;
            quick = quick.next.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

关键点

• 双指针的思想