19.删除链表的倒数第N个节点.md

LeetCode 19.删除链表的倒数第N个节点

描述

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

解一 [暴力解法]

思路

两次遍历

1. 第一次遍历 统计node的总长度
2. 第二次遍历时 删除第n个节点

代码

var removeNthFromEnd = function(head, n) {
    let temp = new ListNode(0);
    temp.next = head;
    let nodeLength = 0;
    // 统计head的总长度
    while(head){
        head = head.next;
        nodeLength++;
    }
    head = temp;
    nodeLength -= n;
    while(nodeLength > 0){
        nodeLength--
        head = head.next;
    }
    head.next = head.next.next;
    return temp.next;
};

解二[数组缓存]

思路

遍历时把所有节点存储到一个数组 cache中 这时的 cache[length-n-1] 位即为要删除的节点

代码

var removeNthFromEnd = function(head, n) {
  let cache = [];
  let temp = head;
  while(temp){
      cache.push(temp);
      temp = temp.next;
  }
  let p = cache[cache.length-n-1];
  if(p){
    p.next = p.next.next;
  }else{
    return head.next;
  }

  return head;
};

解三 [双指针]

思路

使用两个指针 第一个指针 first 先移动 n步 之后第二个指针second再开始移动

知道first移到末尾位置 此时second刚好是第n个节点位置

代码

var removeNthFromEnd = function (head, n) {
  let temp = new ListNode(0);
  temp.next = head;
  let first = temp;
  let second = temp;
  // 首先让第一个指针走n步
  while (n >= 0) {
    n--;
    first = first.next;

  }
  // 在第一个指针到末尾位置时 第二个指针刚好到 第n个节点
  while (first) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return temp.next;
};