Delete The Middle Node Of A Linked List - Leetcode Solution

Problem statement:

Given a singly linked list, delete the middle node. If the linked list has an even number of nodes, delete the second middle node. The node to be deleted is the node at the middle of the linked list.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 2 -> 4 -> 5

Approach:

To delete the middle node of a linked list, we need to find the middle node first. We can do this by using two pointers, a slow pointer and a fast pointer. The slow pointer moves one node at a time, and the fast pointer moves two nodes at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.

Once we have found the middle node, we can delete it by setting the next pointer of the previous node to point to the next node of the middle node.

Algorithm:

1. Initialize a slow pointer and a fast pointer to point to the head of the linked list.
2. Traverse the linked list with the fast pointer moving two nodes at a time and the slow pointer moving one node at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.
3. Initialize a previous pointer to null and a current pointer to point to the head of the linked list.
4. Traverse the linked list with the current pointer until it reaches the middle node. Keep updating the previous pointer to point to the current node.
5. Set the next pointer of the previous node to point to the next node of the middle node.
6. Return the head of the linked list.

Code:

/**

• Definition for singly-linked list.
• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode(int x) : val(x), next(NULL) {}
  

• }; / class Solution { public: ListNode deleteNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; ListNode* prev = nullptr; while (fast != nullptr && fast->next != nullptr) { fast = fast->next->next; prev = slow; slow = slow->next; } if (prev != nullptr) { prev->next = slow->next; delete slow; } else { head = head->next; delete slow; } return head; } };

1