19. 删除链表的倒数第 N 个结点
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
输入：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
题解
思路：利用快慢指针，首先使两指针之间的距离相差 n，然后再同时移动两指针(两指针之间的距离一直保持为 n)，当快指针所指节点的 next 指向"NULL"时，停止移动指针，此时慢指针所指节点的 next 指向的就是需要删除的节点。
代码(C++版本)
ListNode* removeNthFromEnd(ListNode* head, int n) {
//添加一个虚拟头节点
ListNode* headNode = new ListNode(0);
headNode->next = head;
head = headNode;
ListNode* fp = head;
ListNode* sp = head;
for (int i = 0; i < n && fp->next != NULL; i++) {
fp = fp->next;
}
while (fp->next != NULL) {
sp = sp->next;
fp = fp->next;
}
ListNode* tp = sp->next;
sp->next = tp->next;
delete tp;
//删除虚拟头节点
head = headNode->next;
delete headNode;
return head;
}
分析
-
时间复杂度：O(N)
-
空间复杂度：O(1)