刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

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

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

示例：

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

說明：

給定的 n 保證是有效的。

遍歷兩次的算法

首先我們將添加一個(gè)啞結(jié)點(diǎn)作為輔助，該結(jié)點(diǎn)位于列表頭部。啞結(jié)點(diǎn)用來簡(jiǎn)化某些極端情況，例如列表中只含有一個(gè)結(jié)點(diǎn)，或需要?jiǎng)h除列表的頭部。在第一次遍歷中，我們找出列表的長度 L。然后設(shè)置一個(gè)指向啞結(jié)點(diǎn)的指針，并移動(dòng)它遍歷列表，直至它到達(dá)第 (L - n)個(gè)結(jié)點(diǎn)那里。我們把第 (L - n)個(gè)結(jié)點(diǎn)的 next 指針重新鏈接至第 (L - n + 2)個(gè)結(jié)點(diǎn)，完成這個(gè)算法。
簡(jiǎn)單來說，單鏈表刪除要找到當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，將其指向待刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，所以先就是遍歷一次，得到鏈表的長度。

代碼

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

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

遍歷一次的算法

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

假如要?jiǎng)h除倒數(shù)第2個(gè)，所以快指針走3步。
走

走走

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

現(xiàn)在，慢指針也可以出發(fā)了，快慢指針都向前走。當(dāng)快指針指向NULL時(shí)，慢指針指向待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
走

走走

走走走

代碼

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