可视化图解算法：删除链表中倒数第n个节点

1. 题目

描述

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针例如，

给出的链表为: 1→2→3→4→5, n= 2. 删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.

数据范围：链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100

要求：空间复杂度 O(1)，时间复杂度 O(n) 备注：

题目保证 n 一定是有效的

示例1

输入：

{1,2},2

返回值：

{2}

2. 解题思路

删除链表的倒数第n个节点，需要先找到倒数第n个节点的前一个节点，之后再更改前一个节点的指针域，让它指向下下一个节点，这样就可以将倒数第n个节点删除。快速查找倒数第n个节点可以参考上一篇的内容《可视化图解算法：链表中倒数（最后）k个结点》。

假如要删除的链表结构如下图所示，给定的n=2。即需删除倒数第2个节点，也就是4节点。

我们可以采用以下步骤完成倒数第2个节点的删除：

步骤一：定义快慢指针。

步骤二：移动快指针。

快指针移动n次，每次移动一个节点。

步骤三：快慢指针一起移动。

移动快慢指针（条件是：快指针指向节点的下一个节点为Null）。

步骤四：执行删除节点操作。

slow.next=slow.next.next

步骤五：特殊情况处理。

如果要删除的是头节点，如以下链表，给定的n=2。

特殊情况的判断是：快指针移动n步之后，已经指向了Null。

这时，直接返回头节点的下一个节点即可（原头节点删除，返回新的头节点）。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1370265
Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1366721
Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364398

3. 编码实现

3.1 Python编码实现

class ListNode:def __init__(self, x):self.val = x  # 链表的数值域self.next = None  # 链表的指针域# 从链表节点尾部添加节点
def insert_node(node, value):if node is None:print("node is None")return# 创建一个新节点new_node = ListNode(value)cur = node# 找到链表的末尾节点while cur.next is not None:cur = cur.next# 末尾节点的next指针域连接新节点cur.next = new_node# 打印链表（从链表头结点开始打印链表的值）
def print_node(node):cur = node# 遍历每一个节点while cur is not None:print(cur.val, end="\t")cur = cur.next  # 更改指针变量的指向print()#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @param n int整型
# @return ListNode类
#
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:# write code hereif head is None:return head# 1. 定义快慢指针fast = headslow = head# 2. 移动快指针for i in range(n):fast = fast.next# 3. 特殊情况判断：是否删除的是头节点if fast is None:return head.next# 4.对于一般情况，移动快慢指针（条件是：快指针指向节点的下一个节点为None）while fast.next is not None:fast = fast.nextslow = slow.next# 5. 执行删除节点操作slow.next = slow.next.nextreturn headif __name__ == '__main__':head = ListNode(1)insert_node(head, 2)insert_node(head, 3)insert_node(head, 4)insert_node(head, 5)print_node(head)s = Solution()node = s.removeNthFromEnd(head, 2)print_node(node)root = ListNode(1)insert_node(root, 2)print_node(root)node1 = s.removeNthFromEnd(root, 2)print_node(node1)

3.2 Java编码实现

package LL09;public class Main {//定义链表节点static class ListNode {private int val;  //链表的数值域private ListNode next; //链表的指针域public ListNode(int data) {this.val = data;this.next = null;}}//添加链表节点private static void insertNode(ListNode node, int data) {if (node == null) {return;}//创建一个新节点ListNode newNode = new ListNode(data);ListNode cur = node;//找到链表的末尾节点while (cur.next != null) {cur = cur.next;}//末尾节点的next指针域连接新节点cur.next = newNode;}//打印链表（从头节点开始打印链表的每一个节点）private static void printNode(ListNode node) {ListNode cur = node;//遍历每一个节点while (cur != null) {System.out.print(cur.val + "\t");cur = cur.next; //更改指针变量的指向}System.out.println();}public static class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param head ListNode类* @param n    int整型* @return ListNode类*/public ListNode removeNthFromEnd(ListNode head, int n) {// write code hereif (head == null) {return head;}// 1. 定义快慢指针ListNode fast = head;ListNode slow = head;// 2. 移动快指针for (int i = 0; i < n; i++) {fast = fast.next;}// 3. 特殊情况判断：是否删除的是头节点if (fast == null) {return head.next;}// 4. 对于一般情况，移动快慢指针（条件是：快指针指向节点的下一个节点为null）while (fast.next != null) {fast = fast.next;slow = slow.next;}// 5. 执行删除节点操作slow.next = slow.next.next;return head;}}public static void main(String[] args) {ListNode head = new ListNode(1);insertNode(head, 2);insertNode(head, 3);insertNode(head, 4);insertNode(head, 5);printNode(head);Solution solution = new Solution();ListNode node = solution.removeNthFromEnd(head, 2);printNode(node);ListNode root = new ListNode(1);insertNode(root, 2);printNode(root);ListNode node1 = solution.removeNthFromEnd(root, 2);printNode(node1);}
}

3.3 Golang编码实现

package mainimport "fmt"// ListNode 定义链表节点
type ListNode struct {Val  int       //链表的数值域Next *ListNode //链表的指针域
}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @param n int整型* @return ListNode类*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {// write code hereif head == nil {return head}// 1. 定义快慢指针fast := headslow := head// 2. 移动快指针for i := 0; i < n; i++ {//不存在：fast==nil。题目要求：n是有效的，即：n<=链表的长度，此种情况不存在fast = fast.Next}// 3. 特殊情况判断：是否删除的是头节点if fast == nil {return head.Next}// 4. 对于一般情况，移动快慢指针（条件是：快指针指向节点的下一个节点为nil）for fast.Next != nil {fast = fast.Nextslow = slow.Next}// 5. 执行删除节点操作slow.Next = slow.Next.Nextreturn head
}
func main() {head := ListNode{Val: 1}head.Insert(2)head.Insert(3)head.Insert(4)head.Insert(5)head.Print()node := removeNthFromEnd(&head, 2)node.Print()root := ListNode{Val: 1}root.Insert(2)root.Print()node1 := removeNthFromEnd(&root, 2)node1.Print()
}// Insert 从链表节点尾部添加节点
func (ln *ListNode) Insert(val int) {if ln == nil {return}//创建一个新节点newNode := &ListNode{Val: val}cur := ln//找到链表的末尾节点for cur.Next != nil {cur = cur.Next}//末尾节点的next指针域连接新节点cur.Next = newNode
}// Print 从链表头结点开始打印链表的值
func (ln *ListNode) Print() {if ln == nil {return}cur := ln//遍历每一个节点for cur != nil {fmt.Print(cur.Val, "\t")cur = cur.Next //更改指针变量的指向}fmt.Println()
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解。

Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1370265
Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1366721
Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364398

4.小结

删除链表的倒数第n个节点，可以通过以下步骤完成：（1）定义快慢指针；（2）移动快指针；（3）快慢指针一起移动；（4）执行删除节点操作；（5）特殊情况处理。难点是很容易忽略特殊情况的处理。

更多算法视频讲解，你可以从以下地址找到：

Python编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1509965
Java编码实现：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1510007
Golang编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1509945