0. 序言

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之余，來(lái)LeetCode上刷刷簡(jiǎn)單的算法題，如果你對(duì)LeetCode刷題感興趣，歡迎關(guān)注我。

1. 題目描述

請(qǐng)編寫一個(gè)函數(shù)，使其可以刪除某個(gè)鏈表中給定的（非末尾）節(jié)點(diǎn)，你將只被給定要求被刪除的節(jié)點(diǎn)。
現(xiàn)有一個(gè)鏈表 -- head = [4,5,1,9]，它可以表示為:

單鏈表

示例 1:

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

說(shuō)明:

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

模板：

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

2. 解決方案

• 通常辦法

  
  
  鏈表刪除節(jié)點(diǎn)的通常辦法
  
  

  鏈表刪除節(jié)點(diǎn)的通常辦法是找到要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，讓它的next指針指向要?jiǎng)h除的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。如上圖：要想刪除3這個(gè)節(jié)點(diǎn)，只需要讓2這個(gè)節(jié)點(diǎn)的next指針指向4即可。

• 回歸本題
  由于要求刪除指定的節(jié)點(diǎn)，但是卻未告知要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，所以這里我們可以把要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的值賦給要?jiǎng)h除的節(jié)點(diǎn)，然后把要?jiǎng)h除的節(jié)點(diǎn)的next指針指向要?jiǎng)h除的節(jié)點(diǎn)的下下個(gè)節(jié)點(diǎn)即可。

  
  
  1
  
  
  2
  
  
  3
  
  
  4
  
  

  如圖1：想要?jiǎng)h除指定節(jié)點(diǎn)3，可以把節(jié)點(diǎn)4的值賦給節(jié)點(diǎn)3，如圖2，然后可以把節(jié)點(diǎn)3的next指針指向節(jié)點(diǎn)5，如圖3，這樣就相當(dāng)于刪除了節(jié)點(diǎn)3，結(jié)果如圖4。
  因?yàn)橐獎(jiǎng)h除的節(jié)點(diǎn)不是末尾節(jié)點(diǎn)，所以這種辦法可行。

3. 復(fù)雜度分析

時(shí)間和空間的復(fù)雜度都是O(1)

4. Java代碼

/**
 * 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; ②
    }
}

ListNode定義了節(jié)點(diǎn)的內(nèi)容，包括值val，next指針等。
代碼①是把node節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的值賦給node節(jié)點(diǎn)，代碼②是把node節(jié)點(diǎn)的next指針指向下下個(gè)節(jié)點(diǎn)。

5. 后續(xù)

如果大家喜歡這篇文章，歡迎點(diǎn)贊！
如果想看更多 LeetCode 方面的技術(shù)，歡迎關(guān)注!