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).
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode() {}
5 ListNode(int val) { this.val = val; }
6 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7}
8
9public class Solution {
10 public ListNode deleteMiddle(ListNode head) {
11 if (head == null || head.next == null) return null;
12 int count = 0;
13 ListNode temp = head;
14 while (temp != null) {
15 count++;
16 temp = temp.next;
17 }
18 int mid = count / 2;
19 ListNode prev = null;
20 temp = head;
21 while (mid-- > 0) {
22 prev = temp;
23 temp = temp.next;
24 }
25 if (prev != null) {
26 prev.next = prev.next.next;
27 }
28 return head;
29 }
30}
31In the Java solution, a separate class ListNode is used for the node definition. The solution follows the same two-pass approach to remove the middle node.
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
Using JavaScript, this solution employs a two-pointer approach, allowing for efficient traversal and removal of the middle node with a single pass.