Skip to main content

Delete Middle of linked list

The problem at hand involves deleting the middle node of a linked list. Given a singly linked list, we need to remove the middle node from it. The middle node refers to the node that is exactly in the middle of the linked list. If the linked list has an even number of nodes, there could be two middle nodes; however, we will remove only one of them.

Problem Description

Given a singly linked list, the task is to remove the middle node from it. If the linked list has an odd number of nodes, there is a single middle node. If the linked list has an even number of nodes, there are two middle nodes, and we can remove either of them.

Example

Consider the following linked list:

7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

After removing the middle node, the linked list could become:

7 -> 6 -> 5 -> 3 -> 2 -> 1

Or:

7 -> 6 -> 4 -> 3 -> 2 -> 1

Idea to Solve the Problem

Before Delete Middle node

After Delete Middle node

Delete Middle node

To solve this problem, we can use the slow and fast pointer approach. We use two pointers - a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node. We can then remove this middle node by updating the links.

Pseudocode

deleteMiddle(linkedList):
    if linkedList.head is NULL:
        return
    
    slow = linkedList.head
    fast = linkedList.head
    prev = NULL
    
    while fast is not NULL and fast.next is not NULL:
        fast = fast.next.next
        prev = slow
        slow = slow.next
    
    if prev is not NULL:
        prev.next = slow.next
    else:
        linkedList.head = slow.next
    #free(slow)

Algorithm Explanation

  1. Start with both the slow and fast pointers pointing to the head of the linked list, and initialize prev as NULL.
  2. Traverse through the linked list using the fast pointer: a. Move the fast pointer by two steps and the slow pointer by one step. b. Keep track of the previous node using the prev pointer.
  3. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.
  4. Update the links to remove the middle node: a. If the prev pointer is not NULL, set prev.next to slow.next. b. If the prev pointer is NULL, update the head of the linked list to slow.next.
  5. Free the memory occupied by the middle node.

Code Solution

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. We traverse through the linked list once using the slow and fast pointers.

Note that in this linked list are 7 nodes. Then so 4'th position nodes is middle node of this linked list.

Conclusion

This program are working when linked list contain at least three nodes. because if node are less than 3 then there are not possible to find mid node.

And linked list are contain even number of nodes. assuming there are more than two nodes. Then in this case there are possible two middle nodes. Let take an example.

 1-->2-->3-->4-->5-->6-->NULL 

In this situation have 3rd and 4th position nodes are same priority of the mid position. So in this case both algorithm are valid to delete middle of 3rd position or 4th position nodes.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment