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
public class DeleteMiddleLL { public Node deleteMiddleLL[Node node] { if [node == null] { return null; } if [node.getLink[] == null] { return null; } Node first = node, second = node, prev = null; while [second.getLink[] != null && second.getLink[].getLink[] != null] { prev = first; first = first.getLink[]; second = second.getLink[].getLink[]; } if [prev != null] { prev.setLink[first.getLink[]]; first.setLink[null]; } return node; } public void printLL[Node node] { if [node == null] { System.out.println["Linked list is empty"]; } while [node != null] { System.out.println[node.getValue[]]; node = node.getLink[]; } } public static void main[String[] args] { Node node = new Node[1, null]; node.setLink[new Node[2, null]]; node.getLink[].setLink[new Node[3, null]]; node.getLink[].getLink[].setLink[new Node[4, null]]; node.getLink[].getLink[].getLink[].setLink[new Node[5, null]]; DeleteMiddleLL deleteMiddleLL = new DeleteMiddleLL[]; node = deleteMiddleLL.deleteMiddleLL[node]; deleteMiddleLL.printLL[node]; } } public class Node { int value; Node link; public Node[int value, Node link] { this.value = value; this.link = link; } public int getValue[] { return value; } public void setValue[int value] { this.value = value; } public Node getLink[] { return link; } public void setLink[Node link] { this.link = link; } }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 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: Output: User Task: Constraints: Time Complexity - O[N] . In the worst case we may need to delete the node at the end of the list. We can use the approach of slow and fast traversal to delete the middle node in just one traversal. The pseudocode will be like: 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 ].
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.
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.
Your function should return the head of the modified linked list. If the linked list is empty then it should return NULL.
The task is to complete the function deleteMid[] which should delete the middle element from the linked list.
1 next = toDelete->next [Where prevNode is n-1th node and toDelete node is the nth node and toDelete->next is the n+1th 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] && knext;
}
if[p==NULL]{ //at the end
printf["position doesnt exist"];
return;
}
else{ //from the middle
q -> next = p ->next;
free[p];
}
return;
}
}
Space Complexity - O[1].
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.