前端刷题路-Day40：删除链表的倒数第 N 个结点（题号19）

吐槽君发布于 2年前分类：javascript

这是我参与更文挑战的第4天，活动详情查看：更文挑战

删除链表的倒数第 N 个结点（题号19）

题目

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

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

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

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

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

链接

leetcode-cn.com/problems/re…

解释

不得不说这题思路还是挺多的，迭代两次的方法就不提了，就是最普通的解法，重点在于这个进阶：

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

一趟扫描就是只迭代一次，这就有点头疼了，只迭代一次怎么会知道什么时候是最后的第n个元素呢？

笔者想了想之后得到的答案就是记录每次迭代的结果，放到一个数组中，等迭代完成后，从后往前取第n - 1个元素就行，之后进行节点的替换就完事了。

可万万没想到，还有一种双指针解法，确实也是思路清奇啊。

自己的答案（两次迭代）

迭代两次就很简单了，第一次拿到链表的总长度，之后拿总长度减去n，然后再迭代到这个位置，替换其next值即可。

var removeNthFromEnd = function(head, n) {
  var count = -1
      dummyHead = new ListNode(0, head)
      node = dummyHead
  while (node) {
    node = node.next
    count++
  }
  node = dummyHead
  while (count - n) {
    node = node.next
    count--
  }
  node.next = node.next.next
  return dummyHead.next
};

实现比较简单，没啥可说的，需要注意的可能还是count变量，因为开始加了一个节点，所以count初始化值为-1。

自己的答案（栈）

栈这个方法相比两次迭代就更简单了，具体原理在解释部分也说过，先拿到所有节点，都放到一个数组中，然后从后往前数数取值即可。

var removeNthFromEnd = function(head, n) {
  var count = -1
      dummyHead = new ListNode(0, head)
      node = dummyHead
      stack = []
  while (node) {
    stack.push(node)
    node = node.next
    count++
  }
  stack[count - n].next = stack[count - n + 1].next  
  return dummyHead.next
};

同理，为了避免链接就一个元素也被去掉的情况，这里增加了一个头节点，同时将count初始化为-1

更好的方法（双指针）

双指针也不难理解，假设有两个指针，同时在起点出发。

之后快指针先出发，出发到什么位置呢？出发到和慢指针间隔n个节点的位置，此时慢指针再出发，俩指针一块走。

等什么时候快指针为null了，慢指针所在的位置就是我们想要的位置了，再进行操作修改next即可。

但这里同样无法避免链接只有一个元素也被去掉的情况，所以在最后的处理时需要增加一个判断，如果是只有一个链表只有一个元素的话，直接返回链表的next，否则更改慢指针位置的节点。

var removeNthFromEnd = function(head, n) {
  var dummyHead = new ListNode(0, head)
      first = dummyHead
      second = dummyHead
      count = -1
      prenode = null
  while (second) {
    while (count !== n) {
      second = second.next
      count++
    }
    if (second) {
      first = first.next
      second = second.next
      prenode = first
    }
  }
  if (!prenode) {
    head = head.next
  } else {
    prenode.next = prenode.next.next
  }
  return head
};

上面的代码是笔者看了双指针之后自己写的，和正版的答案的区别在于遍历的内部，原版答案的内部赋值条件看起来有点绕，笔者这里索性就将节点值的迭代放在一起了，感觉更清晰一点。

原答案?：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
  let dummyHead = new ListNode('-',head); // 虚拟节点
  
  let p = dummyHead; // 慢指针
  let q = dummyHead; // 快指针
  let count = 0; // 计数器
  let preDelNode = null; // 需要删除节点的前一个节点
  while(q){
    // 快指针先走
    q = q.next;

    // 如果两个指针中间差 n 个节点的时候 慢指针开始走
    if( q && count >= n  ){
      p= p.next;
      preDelNode = p;
    }

    count++;

  }

  // 删除目标节点
  if( !preDelNode ) head = head.next; // 如果没有更新，就说明要删除的是头节点
  else {
    preDelNode.next = preDelNode.next.next;
  }

  return head;
};

其实感觉都可以，看主要看哪种方法用着顺手吧。

PS：想查看往期文章和题目可以点击下面的链接：

这里是按照日期分类的?

前端刷题路-目录（日期分类）

经过有些朋友的提醒，感觉也应该按照题型分类
这里是按照题型分类的?

前端刷题路-目录（题型分类）

有兴趣的也可以看看我的个人主页?

Here is RZ

我来回复

暂无回复内容