700175. Delete Middle of Linked List
Delete Middle of Linked List
Slug: delete-middle-of-linked-list
Difficulty: Easy
Id: 700175
Topic Tags: Linked List, two-pointer-algorithm, Data Structures, Algorithms
Company Tags: Flipkart, Amazon, Microsoft
Summary
Given a singly linked list and an integer k, the task is to delete the middle element of the linked list. If the length of the linked list is odd, the middle element is the one at the (n-1)/2th position (where n is the length of the list), and if it's even, the two middle elements are the ones at the (n/2)-1th and n/2th positions.
Detailed Explanation
The problem can be solved by using a two-pointer algorithm. We maintain two pointers, one at the beginning of the list (p1) and another at the end of the list (p2). The main idea is to keep moving both pointers until they meet in the middle (or one of them becomes null), then delete the node at p2. To find the middle element, we move p1 and p2 simultaneously. If the length of the list is odd, when p1 reaches the middle node, p2 will be null. If the length is even, both pointers will meet at the same time.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers,
p1andp2, to the beginning and end of the linked list respectively. - Move both pointers simultaneously until they meet in the middle (or one of them becomes null).
- If the length of the list is odd, when
p1reaches the middle node,p2will be null. Delete the node atp1. - If the length is even, delete the node at
p2.
Time complexity: O(n), where n is the length of the linked list. Space complexity: O(1), as we are not using any extra space.
Optimized Solutions
Java
public ListNode deleteMiddle(ListNode head, int k) {
if (head == null || head.next == null) {
return null;
}
ListNode p1 = head;
ListNode p2 = head;
for (int i = 0; i < k - 1; i++) {
p2 = p2.next;
}
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
if (p1 == p2) {
return head.next;
} else {
p1.next = p1.next.next;
return head;
}
}