1. Introduction

A common task when working with linked lists is to delete the middle node. If the size of the linked list is even, there will be two middle nodes. In such cases, the second middle is considered for deletion. In this blog post, we will explore a Java program to accomplish this task.

2. Program Steps

1. Create two pointers: slow and fast.

2. Move the fast pointer twice as fast as the slow pointer. By the time the fast pointer reaches the end, the slow pointer will point to the middle of the linked list.

3. Delete the node pointed to by the slow pointer.

4. Handle edge cases for lists with fewer than 2 nodes.

3. Code Program

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head;

    // Function to delete the middle node
    public void deleteMiddle() {
        // Base case: Empty list or only one node
        if (head == null || head.next == null) {
            head = null;
            return;
        }

        Node slow = head;
        Node fast = head;
        Node prev = null;

        // Traverse the list
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }

        // Delete the middle node
        prev.next = slow.next;
    }

    // Function to print the linked list
    void printList() {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }

    // Function to insert a new Node at the last
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.append(1);
        list.append(2);
        list.append(3);
        list.append(4);
        list.append(5);

        System.out.println("Original Linked list:");
        list.printList();

        list.deleteMiddle();

        System.out.println("\nLinked list after deleting the middle:");
        list.printList();
    }
}

Output:

Original Linked list:
1 2 3 4 5
Linked list after deleting the middle:
1 2 4 5

4. Step By Step Explanation

1. We have a Node class to create new nodes for the Linked List.

2. The LinkedList class provides methods to manipulate the linked list, including the deleteMiddle method.

3. The deleteMiddle method employs a slow and a fast pointer technique.

4. As the fast pointer moves twice as fast, when it reaches the end of the list, the slow pointer will be at the middle.

5. The middle node is deleted by setting the next pointer of the node before the middle (tracked by prev) to the node after the middle.

6. In the main method:

a. A LinkedList object is created.

b. Nodes with values 1, 2, 3, 4, 5 are appended.

c. The original list is printed.

d. The middle node 3 is deleted.

e. The modified list is then printed.

Deleting the middle node in a linked list is a common task in coding challenges and demonstrates the concept of slow and fast pointers effectively.