LeetCode19.删除链表的倒数第N个结点
题目
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
思路
删除链表的倒数第N个结点我们可以使用双指针的方法来解决这个问题。我们定义两个指针,分别称为fast和slow,初始时都指向链表的头节点。
- 首先,将fast指针向前移动n个节点,此时fast和slow之间的距离为n。
- 然后,同时将fast和slow指针向前移动,直到fast指针指向链表的最后一个节点。此时,slow指针指向的节点就是要删除的倒数第n个节点的前一个节点。
- 最后,将slow指针所指向的节点的next指针指向slow->next->next,即可删除倒数第n个节点。
- 需要注意的是,如果要删除的是链表的头节点,则需要特殊处理。
Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* fast = dummy;
ListNode* slow = dummy;
for(int i=0 ; i<n; i++)
{
fast = fast->next;
}
//此时fast和slow之间的距离为n
//将fast指向链表的最后一个结点
//那么slow就指向倒数第n个结点的前一个结点
while(fast->next)
{
fast = fast->next;
slow = slow->next;
}
//删除倒数第n个结点
slow->next = slow->next->next;
return dummy->next;
}
};
原文地址:https://blog.csdn.net/Stephen_Curry___/article/details/136216168
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!