Teaching Kids Programming – Delete the Middle Node of a Linked List (Fast and Slow Pointer)


Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Constraints:
The number of nodes in the list is in the range [1, 105].
1 <= Node.val <= 10^5

Hints:
If a point with a speed s moves n units in a given time, a point with speed 2 * s will move 2 * n units at the same time. Can you use this to find the middle node of a linked list?
If you are given the middle node, the node before it, and the node after it, how can you modify the linked list?

Delete the Middle Node of a Linked List (Fast and Slow Pointer)

We use a fast and slow pointer to find the middle node (Teaching Kids Programming – Fast and Slow Pointer to Obtain the Middle of the Linked List). The fast pointer walks two steps at a time while the slow pointer walks one step at a time. When the fast reaches the end, the slow pointer is the middle. In order to delete the middle node, we need to know its previous node which we can keep tracking while we move the slow pointer.

And we use the del to remove the Node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        if not head.next:
            return head.next
        
        fast = slow = head
        prev = None
        
        while fast and fast.next:
            fast = fast.next.next
            prev = slow
            slow = slow.next
            
        prev.next = slow.next
        del slow
        
        return head
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        if not head.next:
            return head.next
        
        fast = slow = head
        prev = None
        
        while fast and fast.next:
            fast = fast.next.next
            prev = slow
            slow = slow.next
            
        prev.next = slow.next
        del slow
        
        return head

The time complexity is O(N) where N is the number of the nodes in the singly linked list.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
630 words
Last Post: Teaching Kids Programming - Draw a Tree in Python using Turtle Graphics (Recursion)
Next Post: Teaching Kids Programming - Sum of Geometric Progression (Math Proof and Python Function)

The Permanent URL is: Teaching Kids Programming – Delete the Middle Node of a Linked List (Fast and Slow Pointer)

Leave a Reply