# 引言
题目链接：https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
# 题目大意
给定一个链表和数字n, 删除链表倒数第n个节点并返回结果链表
Hint: Given n will always be valid.
- Example
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.# 题解
# 一句话题解
快慢指针法, 先行指针先走n步后, 快慢指针再同时前行。这样当先行指针走到链表末尾, 后续指针正好可以操作倒数第n个节点, 直接就地删除即可
# 复杂度
时间复杂度 O(n)
空间复杂度 O(1)
# AC代码
c++版本
class Solution
{
public:
ListNode *removeNthFromEnd(ListNode *head, int n)
{
if (nullptr == head)
{
return nullptr;
}
ListNode *ret = new ListNode();
ret->next = head;
ListNode *pre = ret;
ListNode *cur = ret;
while (n > 0 && nullptr != pre->next)
{
pre = pre->next;
--n;
}
while (nullptr != pre->next)
{
pre = pre->next;
cur = cur->next;
}
pre = cur->next;
cur->next = cur->next->next;
delete (pre);
return ret->next;
}
};go版本
func removeNthFromEnd(head *ListNode, n int) *ListNode {
if nil == head {
return nil
}
ret := &ListNode{0, nil}
ret.Next = head
pre, cur := ret, ret
for n > 0 && nil != pre.Next {
pre = pre.Next
n--
}
for nil != pre.Next {
pre = pre.Next
cur = cur.Next
}
pre = cur.Next
cur.Next = cur.Next.Next
return ret.Next
}
有什么想法，欢迎留下评论。