刪除鏈表的倒數(shù)第N個節(jié)點

題目（remove-nth-node-from-end-of-list）

給定一個鏈表邻悬，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點随闽。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個節(jié)點后父丰，鏈表變?yōu)?1->2->3->5.

說明：

給定的 n 保證是有效的。

遍歷兩次的算法

首先我們將添加一個啞結(jié)點作為輔助掘宪，該結(jié)點位于列表頭部蛾扇。啞結(jié)點用來簡化某些極端情況，例如列表中只含有一個結(jié)點魏滚，或需要刪除列表的頭部镀首。在第一次遍歷中，我們找出列表的長度 L栏赴。然后設(shè)置一個指向啞結(jié)點的指針蘑斧，并移動它遍歷列表，直至它到達(dá)第 (L - n)個結(jié)點那里须眷。我們把第 (L - n)個結(jié)點的 next 指針重新鏈接至第 (L - n + 2)個結(jié)點竖瘾，完成這個算法。
簡單來說花颗，單鏈表刪除要找到當(dāng)前節(jié)點的前一個節(jié)點捕传，將其指向待刪除節(jié)點的下一個節(jié)點，所以先就是遍歷一次扩劝，得到鏈表的長度庸论。

代碼

    /**刪除鏈表的倒數(shù)第N個節(jié)點*/
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //啞結(jié)點用來簡化某些極端情況，例如列表中只含有一個結(jié)點棒呛，或需要刪除列表的頭部
        ListNode dummy = new ListNode(0);
        //放在鏈表頭部
        dummy.next = head;
        int length  = 0;
        //定義一個輔助指針聂示，這個輔助指針有兩個作用
        //第一，用來遍歷出鏈表的長度簇秒，第二鱼喉，用來刪除鏈表節(jié)點
        ListNode first = head;
        //計算長度
        while (first != null) {
            length++;
            first = first.next;
        }
        //計算L=L-n，也就是要遍歷到L-n的位置
        length -= n;
        //first指針的第二個用途，用來刪除鏈表節(jié)點
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        //待刪除節(jié)點的前一個節(jié)點指向待刪除節(jié)點的后一個節(jié)點
        first.next = first.next.next;
        //通過前面定義的輔助指針返回
        return dummy.next;
    }

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

遍歷一次的算法

上述算法可以優(yōu)化為只使用一次遍歷扛禽。我們可以使用兩個指針而不是一個指針锋边。第一個指針從列表的開頭向前移動 n+1 步，而第二個指針將從列表的開頭出發(fā)”嗦現(xiàn)在豆巨，這兩個指針被 n 個結(jié)點分開。我們通過同時移動兩個指針向前來保持這個恒定的間隔掐场，直到第一個指針到達(dá)最后一個結(jié)點往扔。此時第二個指針將指向從最后一個結(jié)點數(shù)起的第 n 個結(jié)點。我們重新鏈接第二個指針?biāo)玫慕Y(jié)點的 next 指針指向該結(jié)點的下下個結(jié)點刻肄。
如圖
現(xiàn)在快慢指針都在頭部瓤球，快指針先走n+1步，則快指針將指前待刪除節(jié)點的前一個節(jié)點敏弃。

假如要刪除倒數(shù)第2個，所以快指針走3步噪馏。
走

走走

走走走
快指針現(xiàn)在已經(jīng)指向了待刪除節(jié)點的前一個節(jié)點麦到。

現(xiàn)在杨赤，慢指針也可以出發(fā)了应民，快慢指針都向前走蒸眠。當(dāng)快指針指向NULL時晾匠，慢指針指向待刪除節(jié)點的前一個節(jié)點配并。
走

走走

走走走

代碼

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;
}