Description
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.
Solution
We could solve this problem by iterating through the list twice, first iteration getting the size of this linked list and the second iteration finding the middle node.
However, we could do it in one pass by using fast slow pointer. i.e. we initialize two nodes, one traverses the list by jumping two nodes at a time, and a slow pointer traverses the list one at a time. This way when the fast pointer reaches the end of the list, the slow pointer will sit right in the middle of the list.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
if (head->next == nullptr) return nullptr;
ListNode *fast = head;
ListNode *slow = head, *slowPrev = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slowPrev = slow;
slow = slow->next;
}
// list size is odd
if (fast->next) {
slowPrev = slow;
slow = slow->next;
}
slowPrev->next = slow->next;
delete slow;
return head;
}
};
The above solution might be more intuitive, below is a more condensed version, but the concept are the same.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
if (head->next == nullptr) return nullptr;
ListNode *fast = head->next->next;
ListNode *slow = head, *temp = nullptr;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
temp = slow->next;
slow->next = slow->next->next;
delete temp;
return head;
}
};