[Problem] Delete the Middle Node of a Linked List

leetcode.com/problems/delete-the-middle-node-of-a-linked-list/

Problem Description

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

In the case above, there are seven nodes in total, and hence the middle node is the node indexed 3, marked in red.

Approach

In order to determine the number of nodes, we traverse through the entire linked list (as there is not size function for a linked list), and derive the middle node.

Afterwards, we go through the linked list once more until we reach the middle node, and then connect the previous node with the node after. In the example above, we would connect 4(index 2), with 1(index 4), essentially taking out the target node.

Solution

def deleteMiddle(self, head):
    obj = head
    cnt = 1
    while obj.next != None:
        obj = obj.next
        cnt += 1
    
    if cnt == 1: 
        return None
    
    target = cnt / 2
    cnt = 0
    change = head

    while change.next:
        cnt += 1
        if cnt == target: 
            change.next = change.next.next
        else: 
            change = change.next

    return head