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

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 447 阅读时长 ≈ 1 分钟

考点

  • 快慢指针/双指针

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
	public:
		ListNode* removeNthFromEnd(ListNode* head, int n) {
			ListNode *dummyHead = new ListNode(-1, head);
			ListNode *slow = dummyHead;
			ListNode *fast = dummyHead;
			while(n--){
				fast = fast->next;
			}
			while(fast->next != nullptr){
				slow = slow->next;
				fast = fast->next;
			}
			slow->next = slow->next->next;
			return dummyHead->next;
		}
};

思路

题目要求删除链表的倒数第 n 个结点，这里需要使用快慢指针来完成这一操作

首先新建一个dummyHead伪节点，链表操作必备；假设我们需要删除链表{1, 2, 3, 4}的倒数第2个节点，即节点3

画图比划一下，用fast指针指向最后一个节点，用slow指针指向倒数第n+1个节点（因为要删除倒数第n个节点）

然后将它们平移到初始位置，是不是一目了然了~

步骤清晰如下：

  1. 快慢指针都从dummyHead起始
  2. 快指针先走n步
  3. 快慢指针一起走，直到快指针到达最后一个节点，此时慢指针的下一个节点就是待删除节点

当然也可以不用快慢指针，使用老办法递归：

  1. 子问题与返回值：每次判断本节点是否应该被删除。若要被删除，则返回next值；若不需要被删除，返回自身

    实际上就是返回应该存在于链表的节点

  2. 递归语句顺序：递归方向分为一去一回，去方向到达临界点后返回；这里选择回方向操作，因为要计算倒数

  3. 临界点：节点为nullptr时返回，意味着nullptr节点存在于链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
	private:
		int n;
		ListNode* recursiveFunc(ListNode* head) {
			if (head == nullptr) return nullptr;
			head->next = recursiveFunc(head->next);
			if (--n == 0) return head->next;
			return head;
		}
	public:
		ListNode* removeNthFromEnd(ListNode* head, int _n) {
			n = _n;
			return recursiveFunc(head);
		}
};