題目

給定一個鏈表, 移除倒數(shù)第n個節(jié)點.

思路

思路和找倒數(shù)第k個數(shù)思路一致,先找一個指針向后移動,當?shù)谝粋€指針移到第k個位置時, 第二個指針開始移動, 第一個指針移到結尾時, 第二個指針移到倒數(shù)第k個.

本題需要刪除節(jié)點, 刪除節(jié)點分為刪除頭部還是刪除其他位置.刪除頭部就直接返回第2個節(jié)點, 刪除其他位置就要找到倒數(shù)第n+1個節(jié)點.

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) {
            // 找到倒數(shù)第n+1個節(jié)點
            temp = head;
        }else if (temp != NULL) {
            temp = temp->next;
        }
    }

    if (temp == NULL) {
        if (k == n) {
            // 移除頭部
            return head->next;
        }
    } else {
        // 移除中間節(jié)點
        temp->next = temp->next->next;
    }

    return head;
}

總結

分析各種情況, 區(qū)分鏈表刪除頭部和刪除其他節(jié)點.

??: 節(jié)點的next可能為null.