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

淩亂°似流年 2023-02-13 05:44 2阅读 0赞

# 删除链表的倒数第N个节点 #

## 一、LeetCode题解 ##

##### 瞧一瞧～ #####

*  博健的LeetCode题解：[Gitbook版本传送门][Gitbook]
 *  博健的LeetCode题解：[CSDN传送门][CSDN]
 *  有趣的CSS：[Gitbook传送门][Gitbook 1]
 *  前端进阶笔记：[Gitbook传送门][Gitbook 2]

## 二、算法题 ##

### 题目 ###

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

**示例：**

给定一个链表: 1->2->3->4->5, 和 n = 2.
    
    当删除了倒数第二个节点后，链表变为 1->2->3->5.

**说明：**

给定的 n 保证是有效的。

**进阶：**

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

## 解法一（二次遍历操作） ##

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

首先我们将添加一个`哑结点`作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。

*  在第一次遍历中，我们找出列表的长度 L。
 *  然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n) 个结点。
 *  把第 (L - n) 个结点的 next 指针重新链接至第 (L - n + 2)个结点。

#### 代码 ####

var removeNthFromEnd = function(head, n) { 
        var current = head
        var len = 0
        while (current) { 
            len++
            current = current.next
        }
        len = len - n
        head = {  val: '', next: head }
        current = head
        while (len != 0) { 
            current = current.next
            len--
        }
        current.next = current.next.next
        return head.next
    }

#### 结果 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2piajY1Njg4Mzl6_size_16_color_FFFFFF_t_70]

## 解法二（快慢指针） ##

*  快指针先跑到第n节点。
 *  之后，慢指针从头节点，与快指针同时走。
 *  快指针走到尾部，慢指针指向了倒数第n个节点

#### 代码 ####

#### 结果 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2piajY1Njg4Mzl6_size_16_color_FFFFFF_t_70 1]

[Gitbook]: https://webbj97.github.io/leetCode-Js/
[CSDN]: https://blog.csdn.net/jbj6568839z/article/details/103808459
[Gitbook 1]: https://webbj97.github.io/Interesting-CSS/
[Gitbook 2]: https://webbj97.github.io/summary/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2piajY1Njg4Mzl6_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200409152312246.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2piajY1Njg4Mzl6,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2piajY1Njg4Mzl6_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200409155152389.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2piajY1Njg4Mzl6,size_16,color_FFFFFF,t_70