/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(42);
dummy.next = head;
// example: n = 2
// dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
// slow
// fast
ListNode slow = dummy;
ListNode fast = dummy;
// dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
// slow
// fast
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
// slow
// fast
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// dummy -> 1 -> 2 -> 3 -> 4 -> 6 ->
// slow
// fast
ListNode removed = slow.next;
slow.next = slow.next.next;
removed.next = null;
return dummy.next;
}
}