Sponsored
Sponsored
This approach involves traversing the list twice. In the first pass, you count the number of nodes to determine the middle node's index. In the second pass, you reach the middle node and update the links to skip it.
Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(1).
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val=0, ListNode next=null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode DeleteMiddle(ListNode head) {
12 if (head == null || head.next == null) return null;
13 ListNode temp = head;
14 int count = 0;
15 while (temp != null) {
16 count++;
17 temp = temp.next;
18 }
19 int mid = count / 2;
20 temp = head;
21 ListNode prev = null;
22 while (mid-- > 0) {
23 prev = temp;
24 temp = temp.next;
25 }
26 if (prev != null) {
27 prev.next = prev.next.next;
28 }
29 return head;
30 }
31}
32This C# solution similarly follows the two-pass logic: first count the nodes to find the middle, then remove it by updating the next pointers.
This approach uses two pointers: a slow pointer and a fast pointer. The fast pointer moves twice as fast as the slow pointer. When the fast pointer reaches the end, the slow pointer will be at the middle node. We can then remove the middle node in a single pass.
Time Complexity: O(n)
Space Complexity: O(1)
1 public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode DeleteMiddle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev != null) {
prev.next = slow.next;
}
return head;
}
}
The C# implementation leverages the two-pointer technique to quickly reach the middle and remove it with minimal operations.