题目
给定一个链表, 移除倒数第n个节点.
思路
思路和找倒数第k个数思路一致,先找一个指针向后移动,当第一个指针移到第k个位置时, 第二个指针开始移动, 第一个指针移到结尾时, 第二个指针移到倒数第k个.
本题需要删除节点, 删除节点分为删除头部还是删除其他位置.删除头部就直接返回第2个节点, 删除其他位置就要找到倒数第n+1个节点.
ListNode* removeNthFromEnd(ListNode* head, int n) {
int k = 0;
ListNode *result = head, *temp = nullptr;
while (result != NULL) {
result = result->next;
k++;
if (k == n+1) {
// 找到倒数第n+1个节点
temp = head;
}else if (temp != NULL) {
temp = temp->next;
}
}
if (temp == NULL) {
if (k == n) {
// 移除头部
return head->next;
}
} else {
// 移除中间节点
temp->next = temp->next->next;
}
return head;
}
总结
分析各种情况, 区分链表删除头部和删除其他节点.
⚠️: 节点的next可能为null.
