LeetCode_19: Remove Nth Node From End of List - LeetCode

# 引言

题目链接：https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

给定一个链表和数字 n, 删除链表倒数第 n 个节点并返回结果链表

Hint: Given n will always be valid.

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)

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
	}