方法一：兩次遍歷算法
思路

我們注意到這個問題可以容易地簡化成另一個問題：刪除從列表開頭數(shù)起的第 (L - n + 1)個結(jié)點猜惋，其中 L 是列表的長度。只要我們找到列表的長度 L专缠，這個問題就很容易解決粹庞。

算法

首先我們將添加一個啞結(jié)點作為輔助疚脐，該結(jié)點位于列表頭部分扎。啞結(jié)點用來簡化某些極端情況，例如列表中只含有一個結(jié)點，或需要刪除列表的頭部坏晦。在第一次遍歷中，我們找出列表的長度 L嫁乘。然后設置一個指向啞結(jié)點的指針昆婿，并移動它遍歷列表，直至它到達第 (L - n) 個結(jié)點那里蜓斧。我們把第 (L - n) 個結(jié)點的 next 指針重新鏈接至第 (L - n + 2)個結(jié)點仓蛆，完成這個算法。

刪除列表中的第 L - n + 1 個元素

Java

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length  = 0;
    ListNode first = head;
    while (first != null) {
        length++;
        first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
        length--;
        first = first.next;
    }
    first.next = first.next.next;
    return dummy.next;
}

復雜度分析

時間復雜度：O(L)挎春，該算法對列表進行了兩次遍歷多律，首先計算了列表的長度 L 其次找到第 (L - n)個結(jié)點痴突。 操作執(zhí)行了 2L-n 步，時間復雜度為 O(L)狼荞。

空間復雜度：O(1)辽装，我們只用了常量級的額外空間。

方法二：一次遍歷算法（快慢指針）
算法

上述算法可以優(yōu)化為只使用一次遍歷相味。我們可以使用兩個指針而不是一個指針拾积。第一個指針從列表的開頭向前移動 n+1 步，而第二個指針將從列表的開頭出發(fā)》嵘妫現(xiàn)在拓巧，這兩個指針被 n 個結(jié)點分開。我們通過同時移動兩個指針向前來保持這個恒定的間隔一死，直到第一個指針到達最后一個結(jié)點肛度。此時第二個指針將指向從最后一個結(jié)點數(shù)起的第 n 個結(jié)點。我們重新鏈接第二個指針所引用的結(jié)點的 next 指針指向該結(jié)點的下下個結(jié)點投慈。

刪除鏈表的倒數(shù)第 N 個元素

Java

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

復雜度分析

時間復雜度：O(L)承耿，該算法對含有 L 個結(jié)點的列表進行了一次遍歷。因此時間復雜度為 O(L)伪煤。

空間復雜度：O(1)加袋，我們只用了常量級的額外空間。