互联网面试宝典

您现在的位置是: 首页 >

问题详情

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

面试宝典 2023-06-12 Web前端开发工程师 15
算法思路:

1. 定义两个指针 slow 和 fast,初始都指向头节点。
2. fast 先往后移动 n 步。
3. 如果此时 fast 为空,说明 n 等于链表长度,则需要删除头节点,直接返回 head->next。
4. 否则,fast 和 slow 同时往后移动,直到 fast 到达链表尾部,此时 slow 指向倒数第 n+1 个节点,将其 next 指向下一个节点的下一个节点,即可删除倒数第 n 个节点。

C++代码实现:

```
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* slow = head;
ListNode* fast = head;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
if (fast == nullptr) {
return head->next;
}
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
```