leecode刷題（20）-- 刪除鏈表中的節(jié)點(diǎn)

刪除鏈表中的節(jié)點(diǎn)

描述：

請編寫一個函數(shù)，使其可以刪除某個鏈表中給定的（非末尾）節(jié)點(diǎn)，你將只被給定要求被刪除的節(jié)點(diǎn)。

現(xiàn)有一個鏈表 -- head = [4,5,1,9]，它可以表示為:

請編寫一個函數(shù)，使其可以刪除某個鏈表中給定的（非末尾）節(jié)點(diǎn)，你將只被給定要求被刪除的節(jié)點(diǎn)。

現(xiàn)有一個鏈表 -- head = [4,5,1,9]，它可以表示為:

image

示例 1:

輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.

示例 2:

輸入: head = [4,5,1,9], node = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9.

說明:

• 鏈表至少包含兩個節(jié)點(diǎn)。
• 鏈表中所有節(jié)點(diǎn)的值都是唯一的。
• 給定的節(jié)點(diǎn)為非末尾節(jié)點(diǎn)并且一定是鏈表中的一個有效節(jié)點(diǎn)。
• 不要從你的函數(shù)中返回任何結(jié)果。

思路：

這道題出的很妙，因?yàn)閺逆湵砝飫h除一個節(jié)點(diǎn) node ，我們最先想到的是修改之前節(jié)點(diǎn)的 next 指針，使其指向之后的節(jié)點(diǎn)。

即：

p.next = p.next.next

但這道題因?yàn)槲覀儫o法訪問我們想要刪除的節(jié)點(diǎn)之前的節(jié)點(diǎn)，所以我們始終不能修改該節(jié)點(diǎn)的 next 指針。我們換種思路，我們將想要刪除的節(jié)點(diǎn)替換為它后面節(jié)點(diǎn)中的值，然后刪除它之后的節(jié)點(diǎn)。這樣我們就完成了題目要求的刪除鏈表中的節(jié)點(diǎn)。

代碼如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

擴(kuò)展：

這里我們可以看到代碼中前面的注釋中有個 ListNode 鏈表類，該類定義如下：

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

此類中包含了指向當(dāng)前值的val，以及指向下一個值的next。