19_删除链表的倒数第N个结点
【问题描述】
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例一：
输入：head = [1], n = 1
输出：[]
示例二：
输入：head = [1,2], n = 1
输出：[1]
提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
【算法设计思想】
在解决本题时，笔者主要是进行了一次遍历链表得到了其长度length，然后再用总长度length减去n得到我们的target，进而问题就迎刃而解了。
在这里我们复习一下单链表中的经典关键语句，求长度的代码：
int length = 0;
while(p != NULL){
p = p -> next;
length++;
}
或者这样写：
int length = 1;
while(p ->next != NULL){
length++;
p = p -> next;
}
【算法描述】
C++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
/**
* 删除链表中倒数第 n 个节点，并返回链表的头节点
*
* @param head 链表的头节点指针
* @param n 需要删除的倒数第 n 个节点
* @return 返回删除节点后的链表头指针
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 1. 计算链表的长度
ListNode* p = head;
int length = 1; // 从1开始计数
while (p->next != nullptr) {
length++;
p = p->next;
}
// 2. 计算需要删除节点的正向位置
int target = length - n;
// 3. 如果需要删除的是头节点
if (target == 0) {
ListNode* temp = head; // 保存当前头节点的指针
head = head->next; // 更新头节点指针
delete temp; // 删除原头节点
return head; // 返回新的头节点
}
// 4. 遍历到目标节点的前一个节点
ListNode* prev = head;
for (int i = 0; i < target - 1; i++) {
prev = prev->next;
}
// 5. 删除目标节点
ListNode* temp = prev->next; // 目标节点
prev->next = temp->next; // 跳过目标节点，重新连接链表
delete temp; // 删除目标节点
// 6. 返回删除后的链表头节点
return head;
}
};
Java：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
* 删除链表中倒数第 n 个节点，并返回链表的头节点
*
* @param head 链表的头节点
* @param n 需要删除的倒数第 n 个节点
* @return 返回删除节点后的链表头节点
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// 1. 计算链表的长度
int length = 1;
ListNode p = head;
while (p.next != null) {
length++;
p = p.next;
}
// 2. 计算需要删除节点的正向位置
int target = length - n;
// 3. 如果需要删除的是头节点
if (target == 0) {
ListNode temp = head; // 保存当前头节点
head = head.next; // 更新头节点为下一个节点
temp = null; // 将原头节点引用设为 null，帮助垃圾回收
return head; // 返回新的头节点
}
// 4. 遍历到目标节点的前一个节点
ListNode prev = head;
for (int i = 0; i < target - 1; i++) {
prev = prev.next; // 移动到目标节点的前一个节点
}
// 5. 删除目标节点
ListNode temp = prev.next; // 目标节点
prev.next = temp.next; // 跳过目标节点，重新连接链表
temp = null; // 将目标节点引用设为 null，帮助垃圾回收
// 6. 返回删除后的链表头节点
return head;
}
}
Python：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# 1. 计算链表的长度
p = head
length = 1 # 初始化长度为1，因为我们将至少有一个节点
while p.next is not None:
length += 1 # 遍历链表，增加长度
p = p.next # 移动指针到下一个节点
# 2. 计算需要删除节点的正向位置
target = length - n
# 3. 如果需要删除的是头节点
if target == 0:
temp = head # 保存当前头节点
head = head.next # 更新头节点为下一个节点
del temp # 删除原头节点
return head # 返回新的头节点
# 4. 遍历到目标节点的前一个节点
prev = head
for i in range(target - 1):
prev = prev.next # 移动指针到目标节点的前一个节点
# 5. 删除目标节点
temp = prev.next # 目标节点
prev.next = temp.next # 跳过目标节点，重新连接链表
del temp # 删除目标节点
# 6. 返回删除后的链表头节点
return head
C：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
// 1. 计算链表的长度
struct ListNode* p = head;
int length = 1; // 初始化长度为1，因为我们将至少有一个节点
while (p->next != NULL) {
length++;
p = p->next; // 移动指针到下一个节点
}
// 2. 计算需要删除节点的正向位置
int target = length - n;
// 3. 如果需要删除的是头节点
if (target == 0) {
struct ListNode* temp = head; // 保存当前头节点
head = head->next; // 更新头节点为下一个节点
free(temp); // 释放原头节点的内存
return head; // 返回新的头节点
}
// 4. 遍历到目标节点的前一个节点
struct ListNode* prev = head;
for (int i = 0; i < target - 1; i++) {
prev = prev->next; // 移动到目标节点的前一个节点
}
// 5. 删除目标节点
struct ListNode* temp = prev->next; // 目标节点
prev->next = temp->next; // 跳过目标节点，重新连接链表
free(temp); // 释放目标节点的内存
// 6. 返回删除后的链表头节点
return head;
}