题目描述:
给你一个链表，删除链表的倒数第 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]
暴力求解:
先找到链表的长度L, 那么应该删除的节点就是第L - n + 1, 但是我们需要找的是删除节点的前一个节点.因此循环次数为L - n 次
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* retNode = new ListNode;
retNode->next = head;
ListNode* dummp = retNode,*curNode = retNode;
//遍历一次链表,得到链表的长度
int L = 0;
while(curNode->next){
L++;
curNode = curNode->next;
}
//寻找删除节点的前一个节点
L = L - n;
while(L--){
dummp = dummp->next;
}
//删除节点
dummp->next = dummp->next->next;
return retNode->next;
}
};
快慢指针:
利用快慢指针的方式, 先同时让快指针(fast)与慢指针(slow)指向一个创建的虚拟节点(retNode), retNode的next域指向头节点(head), 使用虚拟节点的好处是减少对头节点(head)的边界判断以及处理, 然后快指针向后移动n个节点, 随后快慢指针一起向后移动直到快指针(fast)的next域为NULL, 说明此时快指针已经移动到了最后一个节点, 此时慢指针(slow)即为要删除节点的前一个节点, 直接删除掉慢指针(slow)节点的下一个节点, 最后返回虚拟节点(retNode)的next即可.
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* retNode = new ListNode;
retNode->next = head;
ListNode* slow = retNode,*fast = retNode;
while(n--)
fast = fast->next;
while(fast->next){
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return retNode->next;
}
};
