/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteMiddle(ListNode head) {
// base case == list = [1]
if(head.next==null)
return null;
// O(n), O(1)
ListNode slow = new ListNode(-1);
slow.next = head;
ListNode fast = head;
while(fast!=null && fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = slow.next.next;
return head;
}
}