2095. Delete the Middle Node of a Linked List

[songyy5517]

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list. The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

• For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node. 

Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Intuition This problem is basically to find the middle element in a linkedlist. A strightforward idea is to use two pointers, specifically fast & slow pointers, to loop through the entire linked list, where the fast pointer moves two step while the slow pointer moves just one step every iteration. Thereofre, when the fast pointer reaches the end of the linked list, the slow pointer will point to the middle element. In order to delete the middle element, we also need to define a pointer to the preceding element of the slow pointer.

[songyy5517]

Approach: Two Pointers (Fast & Slow)

1. Exception handling;
2. Define fast & slow pointers and a pointer to the preceding node of the slow pointer;
3. Locate the middle element: Loop through the linked list until the fast pointer reaches the end, where the slow and the preceding pointer moves one step per iteration while the fast pointer moves two steps;
4. Delete the middle element through the preceding pointer;
5. Return the head node;

Complexity Analysis

• Time complexity: $O(N)$ , looping through the entire linked list takes $O(N)$ time;
• Space complexity: $O(1)$ , additionally define three pointers, occupying $O(1)$ space.

[songyy5517]

/**
 * 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) {
        // 思路：双指针（快慢指针）
        // 1. 异常处理
        if (head == null || head.next == null)
            return null;

        // 2. 定义双指针
        ListNode slow = head, fast = head.next, pre = null;

        // 3. 定位到中间节点
        while (fast != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next == null ? null : fast.next.next;
        }

        // 4. 产出节点
        pre.next = slow.next;

        return head;
    }
}

[songyy5517]

2024/5/26