前端刷题路-Day40:删除链表的倒数第 N 个结点(题号19)

我心飞翔 分类:javascript

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

删除链表的倒数第 N 个结点(题号19)

题目

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

进阶:你能尝试使用一趟扫描实现吗?

示例 1:

img

输入: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即可。

img

但这里同样无法避免链接只有一个元素也被去掉的情况,所以在最后的处理时需要增加一个判断,如果是只有一个链表只有一个元素的话,直接返回链表的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

回复

我来回复
  • 暂无回复内容