10.7K

8

# Delete middle node linked list Java

**Problem:** For any given linked list, delete middle of the linked list

**Problem Explanation:** For any linked list,

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

Ouput: 1 -> 2 ->4 -> 5

Input: 9 -> 10 ->11 ->12

Ouput: 9 ->11 ->12

**Java Implementation**

**TimeComplexity: O(n)**

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)

Geeks for Geeks

Given a singly linked list, delete the **middle** of the linked list. For example, if the given linked list is 1->2->**3**->4->5 then the linked list should be modified to 1->2->4->5.

If there are **even** nodes, then there would be **two middle **nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6.

If the input linked list is NULL, then it should remain NULL. If the input linked list has 1 node, then this node should be deleted and a new head should be returned.

**Input:**

The first line of input contains a number of test cases T. For each test case, there will be two lines of input, first of which contains number of nodes in the linked list and the next line contains elements in the nodes of the linked list.

**Output:**

Your function should return the head of the modified linked list. If the linked list is empty then it should return NULL.

**User Task:**

The task is to complete the function **deleteMid**() which should delete the middle element from the linked list.

**Constraints:**

1 <=T<= 50

1 <=N<= 1000

1 <=value<= 1000

**Example:Input:**

2

5

1 2 3 4 5

6

2 4 6 7 5 1

**Output:**

1 2 4 5

2 4 6 5 1

**Explanation:Testcase 1**: After deleting middle of the linked list, 3 will be deleted and the list will be as 1, 2, 4, 5.

Approach

Most of the problems related to the linked list can be solved using tracker/pointers i.e slow and fast pointer. In this also we gonna use two pointers first is the slow pointer that will be running one step at a time and the other is the fast pointer that will be running two-step at a time. We start traversing through the linked list and what we find at last…. is our fast pointer reached to the end of the linked list and the slow pointer is in the middle of the linkedList…. Now here we have to keep track of prev of slow pointer also, that will be required to delete the middle node.

while(fast!=null && fast.next!=null){

prev = slow;

slow = slow.next;

fast = fast.next.next;

}

if(prev!=null){

prev.next = slow.next;

}

Check Out Code at

GitHub—

https://github.com/Ysunil016/Java_Coding_Challenges/blob/master/GeeksForGeeks/src/LinkedList/DeleteMiddleNode.java

In this problem, we will delete the Middle Node from a given Linked List. We have covered the algorithm (along with implementation) to delete the middle node from a Singly Linked List and Doubly Linked List.

We will go through some of the basics of Linked List and the delete operation to remove a given node in a Linked List and then, move to our main topic. The challenge is to **identify the node to delete that is the middle node in the given Linked List**.

Linked List is a one of the DataStructure used for storing collection of data. A Linked List has the following properties:

- A Linked List is linear dynamic DataStructure.
- The number of nodes in Linked List is not fixed, it can grow and shrink on demand.
- Each node of the Linked List is made up of two items - the data and a reference to the next node.
- The Last node has reference to null.
- The entry point is called
**head** - If the list is empty then the head is null reference.

Basic Structure of Linked List-

- The size of array must be known in advance before using it in program.
- Increasing size of the array is a time taking process. It almost impossible and to increase the size of an array at runtime.
- As array stored in our memory contiguously , inserting and deleting an element in an array means shifting of all the elements.

The Linked List consists of series of structures called Nodes. We can think of each node as a record. The first part stores the data , and second part stores a pointer to the next node. So , conclusion is each node contains two field , a data field and and next field. Generally , Linked List means Singly Linked List. In Singly Linked List , the link of the last node in the list is NULL, which indicates the end of the list.

Each Node is allocated in the heap with call to malloc() , so node memory contimues to exists until it is explicitly deallocated.

The node which is called as head is the first node in the list. The last node's next pointer points to NULL value.

struct ListNode { // define ListNode in Linked List int data; // the data struct ListNode *next; //pointer to the next List Node. };## Deletion Operation on a List-

In this article we will talk about deleting an intermediate Node in Singly Linked List.

In this case, the node to be removed is always located between two nodes. Head and tails links are not updated in this case. It is done in two steps -

- Start Traversing the Linked List, Once we find the node to be deleted , change the previous node's next pointer to the next pointer of the node to be deleted.

- Dispose the current node to be deleted.

## How to find the middle element?

To find the middle element, we can take two approaches:

- Uisng 2 traversals: The first traversal to find number of elements and the second traversal to find the middle element
- Using 1 traversal with slow and fast pointers

Go through this article to get the complete idea

As we just need to position of middle element, we can get it using one traversal to count the total number of elements:

// one traversal int count_middle_position(Node head) { int count = 0; if(head != null) ++ count; Node temp = head; while(temp.next != null) { ++ count; temp = temp.next; } return count / 2; }- Get the position of the middle node using the above techniques (say nth position).
- Traverse to the nth node of the singly linked list and also keep reference of n- 1 th node in some temp variable say prevnode.

- Reconnect the n-1 th node with the n+1 th node i.e. prevNode->next = toDelete->next (Where prevNode is n-1th node and toDelete node is the nth node and toDelete->next is the n+1th node).

- Free the memory occupied by the n th node i.e. toDelete node.

## Implementation in C

void *delete(struct listNode **head , int position) { int k=1; struct listNode *p, *q; if(*head==NULL){ printf("List Empty"); return; } p = *head; //initialize p with head pointer or first node. if(position == 1){ //from beginning *head = (*head)->next; free(p); return; } else{ //transverse the list until arriving at the position from which we want to delete while((p!=NULL) && k<position){ k++; q=p; p = p->next; } if(p==NULL){ //at the end printf("position doesnt exist"); return; } else{ //from the middle q -> next = p ->next; free(p); } return; } }**Time Complexity** - O(N) . In the worst case we may need to delete the node at the end of the list.

**Space Complexity** - O(1).

We can use the approach of slow and fast traversal to delete the middle node in just one traversal. The pseudocode will be like:

// one traversal int middle_element(Node head) { Node first_node = head, second_node = head; if(head == null) return; while(first_node != null && second_node != null) { first_node = first_node.next; second_node = second_node.next.next; } delete(first_node); }Apart from Singly Linked List , we also have two others types of Linked List i.e. Doubly Linked List and Circular Linked List.

We will look the structures of both the types and brief about how we can delete an intermediate node from these two.

A Doubly Linked List contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

The advantage of Doubly Linked List is that given a node in the list, we can navigate in both direction. In Doubly Linked List we can delete a node even we dont have previous node address ( since we have previous pointer ).

The disadvantage of Doubly Linked List are - Eachnmnode requires an extra pointer, requiring more space. The insertion and deletion of a node takes a bit longer.

In this case, the node to be removed is always located between two nodes, and heads and tails are not updated, the removal can be done in two steps-

- Maintain the previous node while also traversing the list. Upon locating the node to be deleted , change the previous node's next pointer to the next node of the node to be deleted. Also, change the previous pointer of the next node to the node to be deleted to the point to the previous node of the node to be deleted.
- Dispose the current Node to be deleted.

**Time Complexity** - O(N).

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Advantages of Circular Linked List are as follow -

- Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.
- Useful for the implementations of queues.

Hope this article helps you understands the concept of Deletion in Linked List.

10