LeetCode 的 C++ 实现（十）删除链表的倒数第N个节点

节点"/>

LeetCode 的 C++ 实现（十）删除链表的倒数第N个节点

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

示例：

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

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

给定的 n 保证是有效的。

暴力解法

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyNode = new ListNode(0);dummyNode->next = head;ListNode* pWork = head;int size = 0;while(pWork != nullptr){pWork = pWork->next;size++;}int target = size + 1 -n;pWork = dummyNode;for(int times = 1; times < target ; times++){pWork = pWork->next;}pWork->next = pWork->next->next;return dummyNode->next;}
};

双指针法

1. 设置虚拟节点 dummyHead 指向 head
2. 设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
3. 移动 q，直到 p 与q 之间相隔的元素个数为 n
4. 同时移动 p 与 q，直到 q 指向的为 NULL
5. 将 p 的下一个节点指向下下个节点

    ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* first = dummy;ListNode* second = dummy;// Advances first pointer so that the gap between first and second is n nodes apartfor (int i = 1; i <= n + 1; i++) {first = first->next;}// Move first to the end, maintaining the gapwhile (first != nullptr) {first = first->next;second = second->next;}second->next = second->next->next;return dummy->next;