LeetCode 19. 删除链表的倒数第N个节点

Scroll Down

题目

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

解答

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		// 创建头结点,避免空链表的情况
		ListNode *dummy = new ListNode(0);
		dummy->next = head;
		ListNode *fast = dummy;
		ListNode *slow = dummy;
		// 因为创建了头结点,所以让快指针先走n+1步
		for (int i = 1; i <= n + 1; i++) {
			fast = fast->next;
		}
		// 寻找要删除结点的前一个结点
		while (fast != NULL) {
			fast = fast->next;
			slow = slow->next;
		}
		slow->next = slow->next->next;
		return dummy->next;
	}
};