20679dc40d996bd414898f1f0acfc5de
(难度Medium) Problem 19: Remove Nth Node From End of List

Problem 19: Remove Nth Node From End of List

链接

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

难度等级

Medium

题干

Given a linked list, remove the n-th node from the end of list and return its head.

题意

题意是给定一个链表,要求删除从后往前数第n个元素

样例

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

注意:n始终有效

题解

在我们解决这道问题之前,我们先做一个小小的思考。如果题中需要删除的不是一个链表,而是一个数组,那么应该怎么操作呢?

这个想必大家都会,既然是数组,那么数组的长度就是可知的。那么倒数第n个元素也就可以直接求出来,剩下的就是移动n后面的元素,使得数组减少一位。

链表的优势在于删除元素不需要移动剩余元素,但是链表的缺点在于链表不知道长度,无法快速访问当中的某一个元素。

解法一 两次遍历

由于我们要删除的是倒数第n个元素,在链表当中我们无法获取元素的位置也无法直接根据位置获取元素。要想知道倒数第n个元素是什么,我们需要首先遍历一次链表,获取到链表的长度,这样我们就可以算出来它是正数第几个数了。

有了正数的顺序,就可以从头开始遍历到这个元素,然后把它的next指向next的next即可。

解法二 一次遍历

官方还提供了另一种解法,可以只遍历一次找到答案。

其实思路很简单,我们一次遍历的时候,只用了一个指针,如果我们多用一个指针就可以实现。具体怎么做呢?首先先拿出一个指针i,先跑n长度的距离。接着指针i和j同时以同样的速度跑,当i跑到末尾的时候,i所在的位置就是倒数第n个元素的位置。那么我们操作j指针,删掉它后面这个元素即可,用一张图可以非常直观地理解:

top Created with Sketch.