題目描述

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

示例：
輸入：1->2->3->4->5 和 2
輸出：1->2->3->5

解析

考察重點(diǎn)：鏈表的遍歷和刪除結(jié)點(diǎn)操作

定位倒數(shù)第n個結(jié)點(diǎn)，操作第n個結(jié)點(diǎn)前驅(qū)的next引用指向第n個結(jié)點(diǎn)后繼。

實(shí)現(xiàn)方法：

1. 方法一：可以分兩次遍歷，第一遍統(tǒng)計(jì)整個鏈表的長度，計(jì)算倒數(shù)第n個結(jié)點(diǎn)位置；第二遍定位目標(biāo)結(jié)點(diǎn)完成刪除操作。時間復(fù)雜度O(2n)。
2. 方法二：雙指針實(shí)現(xiàn)。第一個指針首先向前移動n-1位，然后兩個指針同時移動直到第一個指針到達(dá)鏈表最后一個結(jié)點(diǎn)為止，此時第二個指針就是倒數(shù)第n個結(jié)點(diǎn)。時間復(fù)雜度O(n)。

實(shí)現(xiàn)技巧：

使用效率更高的方法二實(shí)現(xiàn)，但是需要做一些處理。

• 因?yàn)槿绻绶椒ǘ觯谝粋€指針首先向前移動n-1位，兩個指針遍歷完之后第二個指針指向的時倒數(shù)第n個結(jié)點(diǎn)，這時沒有辦法操作起前驅(qū)的next引用，又需要遍歷一次鏈表；
• 再者如果第一指針試圖移動n位，則如果鏈表恰好長度小于等于n時。無法快速斷定第二個指針是剛好倒數(shù)第n個元素還是鏈表不存在倒數(shù)第n個元素，需要額外判斷。
• 定義一個頭結(jié)點(diǎn)結(jié)點(diǎn)，其next引用指向鏈表的第一個結(jié)點(diǎn)。這樣第一個指針移動n位，第二個指針就一定為倒數(shù)第n個結(jié)點(diǎn)的前一位，即倒數(shù)n-1結(jié)點(diǎn)；若移動小于n位，則證明鏈表中不存在倒數(shù)第n個結(jié)點(diǎn)。

代碼

private class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public ListNode removeNthFromEnd(ListNode head, int n) {
    if(n <= 0){
        return head;
    }
    if(null == head){
        return head;
    }
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;
    ListNode first = sentinel;
    ListNode second = sentinel;
    int i = 0;
    for(; i < n && first.next != null ; ++i){//first指針嘗試移動n位
        first = first.next;
    }
    if(i<n){//移動距離小于n，說明鏈表中不存在倒數(shù)第n個結(jié)點(diǎn)
        return head;
    }
    //移動距離等于n，證明存在倒數(shù)第n個節(jié)點(diǎn)。兩個指針一起移動直到第一個指向到達(dá)最后一個結(jié)點(diǎn)
    while(first.next != null){
        second = second.next;
        first = first.next;
    } 
    //記錄要刪除的結(jié)點(diǎn)
    ListNode delNode = second.next;
    //修改指針刪除結(jié)點(diǎn)
    second.next = delNode.next;
    delNode.next = null;//刪除結(jié)點(diǎn)的next置null，幫助GC回收刪除結(jié)點(diǎn)
    //因?yàn)閔ead結(jié)點(diǎn)可能會被刪除，所以不可以直接返回head，要返回sentinel.next
    head = sentinel.next;
    sentinel.next = null;//幫助GC回收sentinel結(jié)點(diǎn)
    return head;
}

實(shí)現(xiàn)方法2：

可以不定義作為哨兵的頭結(jié)點(diǎn)，我們直接移動第一個指針n次。這里分成3種情況思考：

1. 如果節(jié)點(diǎn)數(shù)少于n，那么移動的次數(shù)小于n。
2. 如果節(jié)點(diǎn)數(shù)等于n，移動的次數(shù)剛好是n，并且第一個指針指向null，不動的指針指向的就是倒數(shù)第n個節(jié)點(diǎn)。
3. 如果節(jié)點(diǎn)數(shù)大于n，移動n次后，第一個指針指向一個存在的節(jié)點(diǎn)，而不動的指針指向的是倒數(shù)第n+1個節(jié)點(diǎn)。

代碼也按照這個邏輯進(jìn)行編寫

代碼2

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(n <= 0){
        return head;
    }
    if(null == head){
        return head;
    }
    int i = 0;
    ListNode tail = head;
    while(tail != null && i < n){
        tail = tail.next;
        i++;
    }
    //節(jié)點(diǎn)數(shù)量小于n
    if(i < n){
        return head;
    } 
    //節(jié)點(diǎn)數(shù)量等于n
    if(tail == null){
        head = head.next;
        return head;
    }
    //節(jié)點(diǎn)數(shù)量大于n
    ListNode newHead = head;
    while(tail.next != null){
        head = head.next;
        tail = tail.next;
    }
    head.next = head.next.next;
    return newHead;
}

LeetCode上執(zhí)行結(jié)果

LeetCode上代碼2執(zhí)行結(jié)果