赞
踩
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
注意使用虚拟头结点,这样方面处理删除实际头结点的逻辑。
fast首先走n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作) 。
- class Solution {
- public:
- ListNode* removeNthFromEnd(ListNode* head, int n) {
- ListNode* dummy = new ListNode;
- dummy->next = head;
- ListNode* fast = dummy;
- ListNode* slow = dummy;
- for(int i = 0; i < n + 1; i++)
- {
- fast = fast->next;
- }
- while(fast != nullptr)
- {
- fast = fast->next;
- slow = slow->next;
- }
- slow->next = slow->next->next;
- return dummy->next;
- }
- };

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。