#include "s0019_remove_nth_node_from_end_of_list.hpp"

// 思路一：遍历两次，第一次遍历得到总长度，第二次遍历找出倒数第 n 个
// 思路二：栈，先进后出，全部入栈后弹出倒数第 n 个把它舍弃掉
// 思路三：双指针，快指针比慢指针多走 n
// 步，等快指针走到头时，慢指针指向的的就是倒数第 n 个

// 双指针实现
ListNode* S0019::removeNthFromEnd(ListNode* head, int n) {
  // 一种常见的处理头指针的方法是添加一个哑指针，这个哑指针指向头指针
  // 这样我们就不需要单独讨论头指针了。
  ListNode dummy(0, head);
  ListNode* fast = &dummy;
  for (int i{0}; i < n; i++) {
    if (fast == nullptr) {
      return nullptr;
    } else {
      fast = fast->next;
    }
  }
  ListNode* slow = &dummy;
  while (fast->next != nullptr) {
    fast = fast->next;
    slow = slow->next;
  }
  slow->next = slow->next->next;
  return dummy.next;
}