Leetcode.19. Remove Nth Node From End of List

题目

给定一个链表, 移除倒数第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.