leetCode 019 删除链表倒数第n个结点

leetCode 019 删除链表倒数第n个结点

题目描述：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例输入输出：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
输入：head = [1], n = 1
输出：[]
输入：head = [1,2], n = 1
输出：[1]

思路：

利用栈一次遍历

先遍历一次，将链表所有结点压入栈，再根据n遍历一次，弹出结点，直到弹出第n个结点，栈顶为其前驱结点，此结点直接指向它的下一个结点的next即可。
参数：
- 防止删除第一个节点的超前指针dummy；用于遍历的指针p；指向需要删除结点的上一个结点的指针pre。
终止条件：
- 弹出第n个元素。
迭代前要做的事情：
- 创建一个超前指针dummy，此指针的next指向head，防止要删除第一个结点无法返回的情况。
迭代过程中做的事：
- 第一次迭代：
  - 压入链表的结点。
- 第二次迭代：
  - 弹出链表的结点。
迭代后要做的事：
- pre指向栈顶元素。
- pre的next指向pre的下一个结点的next
复杂度分析：
- 时间复杂度：最差的情况遍历两次，O（N^2）
- 空间复杂度：需要用栈装链表，O（N）
代码：

/**
* 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 removeNthFromEnd(ListNode head, int n) {
      ListNode dummy = new ListNode(0, head);
      Stack<ListNode> stack = new Stack<>();
      if(n == 0){
          return head;
      } 
      ListNode p = dummy;
      while(p != null){
          stack.push(p);
          p = p.next;
      }
      for(int i = 0; i < n; i++){
          p = stack.pop();
      }
      ListNode pre = stack.peek();
      pre.next = pre.next.next;
      return dummy.next;
  }
}

快慢指针一次遍历

用快慢指针，fast比slow快n+1步，当fast指向null时，slow指向需要被删除节点的前一个结点。
参数：
- 快指针fast，慢指针slow，超前虚拟指针dummy。
终止条件：
- fast指向null
迭代前要做的事：
- slow指向dummy，fast指向head。
- fast向前走n步。
迭代过程中要做的事：
- fast指向next。
- slow指向next。
迭代后要做的事：
- slow指向下一个结点的next
复杂度分析：
- 时间复杂度：只需要遍历一遍，O（n）
- 空间复杂度：不需要额外的空间，O（1）
代码：

/**
* 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 removeNthFromEnd(ListNode head, int n) {
      ListNode dummy = new ListNode(0, head);

      ListNode fast = head, slow = dummy;
      for(int i = 0; i < n; i++){
          fast = fast.next;
      } 
      while(fast != null){
          fast = fast.next;
          slow = slow.next;
      }
      slow.next = slow.next.next;
      return dummy.next;
  }
}