題目描述（中等難度）

給定一個(gè)鏈表，將倒數(shù)第 n 個(gè)結(jié)點(diǎn)刪除。

解法一

刪除一個(gè)結(jié)點(diǎn)，無非是遍歷鏈表找到那個(gè)結(jié)點(diǎn)前邊的結(jié)點(diǎn)，然后改變下指向就好了。但由于它是鏈表，它的長(zhǎng)度我們并不知道，我們得先遍歷一遍得到它的長(zhǎng)度，之后用長(zhǎng)度減去 n 就是要?jiǎng)h除的結(jié)點(diǎn)的位置，然后遍歷到結(jié)點(diǎn)的前一個(gè)位置就好了。

public ListNode removeNthFromEnd(ListNode head, int n) {
    int len = 0;
    ListNode h = head;
    while (h != null) {
        h = h.next;
        len++;
    }
    //長(zhǎng)度等于 1 ，再刪除一個(gè)結(jié)點(diǎn)就為 null 了
    if (len == 1) {
        return null;
    }

    int rm_node_index = len - n;

    //如果刪除的是頭結(jié)點(diǎn)
    if (rm_node_index == 0) {
        return head.next;
    }

    //找到被刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
    h = head;
    for (int i = 0; i < rm_node_index - 1; i++) {
        h = h.next;
    }

    //改變指向
    h.next = h.next.next;
    return head;
}

時(shí)間復(fù)雜度：假設(shè)鏈表長(zhǎng)度是 L ，那么就第一個(gè)循環(huán)是 L 次，第二個(gè)循環(huán)是 L - n 次，總共 2L - n 次，所以時(shí)間復(fù)雜度就是 O（L）。

空間復(fù)雜度：O（1）。

我們看到如果長(zhǎng)度等于 1 和刪除頭結(jié)點(diǎn)的時(shí)候需要單獨(dú)判斷，其實(shí)我們只需要在 head 前邊加一個(gè)空節(jié)點(diǎn)，就可以避免單獨(dú)判斷。

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

解法二 遍歷一次鏈表

上邊我們遍歷鏈表進(jìn)行了兩次，我們?nèi)绾沃槐闅v一次呢。

看了 leetcode 的講解。

想象一下，兩個(gè)人進(jìn)行 100m 賽跑，假設(shè)他們的速度相同。開始的時(shí)候，第一個(gè)人就在第二個(gè)人前邊 10m ，這樣當(dāng)?shù)谝粋€(gè)人跑到終點(diǎn)的時(shí)候，第二個(gè)人相距第一個(gè)人依舊是 10m ，也就是離終點(diǎn) 10m。

對(duì)比于鏈表，我們?cè)O(shè)定兩個(gè)指針，先讓第一個(gè)指針遍歷 n 步，然后再讓它倆同時(shí)開始遍歷，這樣的話，當(dāng)?shù)谝粋€(gè)指針到頭的時(shí)候，第二個(gè)指針就離第一個(gè)指針有 n 的距離，所以第二個(gè)指針的位置就剛好是倒數(shù)第 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;
    //第一個(gè)指針先移動(dòng) n 步
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    } 
    //第一個(gè)指針到達(dá)終點(diǎn)停止遍歷
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
} 

時(shí)間復(fù)雜度：

第一個(gè)指針從 0 到 n ，然后「第一個(gè)指針再從 n 到結(jié)束」和「第二個(gè)指針從 0 到倒數(shù)第 n 個(gè)結(jié)點(diǎn)的位置」同時(shí)進(jìn)行。

而解法一無非是先從 0 到 結(jié)束，然后從 0 到倒數(shù)第 n 個(gè)結(jié)點(diǎn)的位置。

所以其實(shí)它們語句執(zhí)行的次數(shù)其實(shí)是一樣的，從 0 到倒數(shù)第 n 個(gè)結(jié)點(diǎn)的位置都被遍歷了 2 次，所以總共也是 2L - n 次。只不過這個(gè)解法把解法一的兩次循環(huán)合并了一下，使得第二個(gè)指針看起來是順便遍歷，想法很 nice。

所以本質(zhì)上，它們其實(shí)是一樣的，時(shí)間復(fù)雜度依舊是 O（n）。

空間復(fù)雜度：O（1）。

解法三

沒看講解前，和室友討論下，如何只遍歷一次鏈表。室友給出了一個(gè)我竟然無法反駁的觀點(diǎn)，哈哈哈哈。

第一次遍歷鏈表確定長(zhǎng)度的時(shí)候，順便把每個(gè)結(jié)點(diǎn)存到數(shù)組里，這樣找結(jié)點(diǎn)的時(shí)候就不需要再遍歷一次了，空間換時(shí)間？？？哈哈哈哈哈哈哈哈哈。

public ListNode removeNthFromEnd(ListNode head, int n) {
    List<ListNode> l = new ArrayList<ListNode>();
    ListNode h = head;
    int len = 0;
    while (h != null) {
        l.add(h);
        h = h.next;
        len++;
    }
    if (len == 1) {
        return null;
    }
    int remove = len - n;
    if (remove == 0) {
        return head.next;
    }
    //直接得到，不需要再遍歷了
    ListNode r = l.get(remove - 1);
    r.next = r.next.next;
    return head;
}

時(shí)間復(fù)雜度：O（L）。

空間復(fù)雜度：O（L）。

總

利用兩個(gè)指針先固定間隔，然后同時(shí)遍歷，真的是很妙！另外室友的想法也很棒，哈哈哈哈哈。

更多詳細(xì)通俗題解詳見 leetcode.wang 。