5
LeetCode 第 19 号问题：删除链表的倒数第 N 个节点
source link: https://www.cxyxiaowu.com/6851.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 第 19 号问题：删除链表的倒数第 N 个节点-程序员小吴
当前位置：程序员小吴 > LeetCodeAnimation > LeetCode 第 19 号问题：删除链表的倒数第 N 个节点
本文首发于公众号「五分钟学算法」，是图解 LeetCode 系列文章之一。
题目来源于 LeetCode 上第 19 号问题：删除链表的倒数第 N 个节点。题目难度为 Medium，目前通过率为 34.4% 。
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
采取双重遍历肯定是可以解决问题的，但题目要求我们一次遍历解决问题，那我们的思路得发散一下。
我们可以设想假设设定了双指针p和q的话，当q指向末尾的NULL，p与q之间相隔的元素个数为n时，那么删除掉p的下一个指针就完成了要求。
- 设置虚拟节点
dummyHead指向head - 设定双指针
p和q，初始都指向虚拟节点dummyHead - 移动
q，直到p与q之间相隔的元素个数为n - 同时移动
p与q，直到q指向的为NULL - 将
p的下一个节点指向下下个节点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* p = dummyHead;
ListNode* q = dummyHead;
for( int i = 0 ; i < n + 1 ; i ++ ){
q = q->next;
}
while(q){
p = p->next;
q = q->next;
}
ListNode* delNode = p->next;
p->next = delNode->next;
delete delNode;
ListNode* retNode = dummyHead->next;
delete dummyHead;
return retNode;
}
};
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK