題目介紹

題目：刪除鏈表的倒數(shù)第N個節(jié)點
描述：給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。
示例:
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.
說明：給定的 n 保證是有效的。
進(jìn)階：你能嘗試使用一趟掃描實現(xiàn)嗎？

解析

如果是兩次掃描，這個問題是十分簡單的，第一次掃描確認(rèn)鏈表的長度，第二次根據(jù)長度算出目標(biāo)結(jié)點的位置并刪除。而僅使用一次掃描，就意味著我們無法算出鏈表的長度，從而也就無法知道目標(biāo)結(jié)點的確切位置了。

雖然無法確認(rèn)目標(biāo)結(jié)點的確切位置，但是我們知道它與終點的相對位置，也就可以知道它相對于鏈表中點的對稱點的位置?，F(xiàn)在，我們讓一個指針在起點位置，一個指針在目標(biāo)結(jié)點的對稱點處，如下所示：

雙指針

因為對稱的原因，第N個結(jié)點到終點的距離和倒數(shù)第N個結(jié)點到起點的距離一致。也就是說，如果指針1和指針2同時向后移動，當(dāng)指針2走到終點時，指針1的位置正好是倒數(shù)第N個結(jié)點，也就是目標(biāo)結(jié)點。參考代碼如下：

public static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode first = new ListNode(0);
    first.next = head;
    ListNode node1 = first;
    ListNode node2 = first;
    int i = 0;
    while (i<n) {
        node1 = node1.next;
        i++;
    }

    while (node1.next!=null) {
        node1 = node1.next;
        node2 = node2.next;
    }

    node2.next = node2.next.next;

    return first.next;
}

總結(jié)

求出鏈表的長度再進(jìn)行刪除是基于絕對位置來計算的，而在無法提前得知長度時，相對位置也可以做到同樣的事，有時候換個角度思考，可能會有意外的驚喜哦。

相關(guān)源碼已經(jīng)上傳到我的Github。

下題預(yù)告

題目：有效的括號
描述：給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。

示例 1:
輸入: "()"
輸出: true

示例 2:
輸入: "()[]{}"
輸出: true

示例 3:
輸入: "(]"
輸出: false

示例 4:>
輸入: "([)]"
輸出: false

示例 5:
輸入: "{[]}"
輸出: true

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。