【力扣LeetCode】19 删除链表的倒数第N个节点

本文主要是介绍【力扣LeetCode】19 删除链表的倒数第N个节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述（难度中）

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

链接

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

思路

用一前一后两个指针，第一个指针先跑n个node，第二个指针再从头跑，第一个指针跑到结尾时，第二个指针指向的node即为要删除的node。
注意：
1、输入的链表没有n个node时，返回NULL
2、要删除的node是第一个node时，返回为head->next，这种情况需要特判
3、需要用一个指针记录指向要删除node的上一个node

代码

代码没有释放p2指向的内存空间，因为使用delete和free都会编译出错，实际操作中是需要释放的。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* p1 = head;ListNode* p2 = head;ListNode* p2pre = head;// p1 先向前跑n下while(n--){if(p1){p1 = p1->next;}else{return NULL;}} // 删除的是第一个node时的特判if(p1 == NULL){return head->next;}while(p1){p1 = p1->next;p2pre = p2;p2 = p2->next;}p2pre->next = p2->next;return head;}
};