題⽬描述

給定單向鏈表的頭指針和⼀個要刪除的節點的值，定義⼀個函數刪除該節點。返回刪除後的鏈表的頭節點。

1. 此題對⽐原題有改動
2. 題⽬保證鏈表中節點的值互不相同
3. 該題只會輸出返回的鏈表和結果做對⽐，所以若使⽤ C 或 C++ 語⾔，你不需要 free 或 delete 被刪除的節點

數據範圍:

• 0<=鏈表節點值<=10000
• 0<=鏈表⻓度<=10000

示例1

輸⼊：{2,5,1,9},5
返回值：{2,1,9}
説明：給定你鏈表中值為 5 的第⼆個節點，那麼在調⽤了你的函數之後，該鏈表應變為 2 -> 1 -> 9

示例2

輸⼊：{2,5,1,9},1
返回值：{2,5,9}
説明：給定你鏈表中值為 1 的第三個節點，那麼在調⽤了你的函數之後，該鏈表應變為 2 -> 5 -> 9

思路及解答

虛擬頭節點

如果要刪除鏈表⾥⾯的⼀個節點，其實就是將前置節點的next 直接指向當前節點的後置節點，這樣在鏈表中再也找不到該節點了，也就是相當於刪除了。

假設有⼀個鏈表，我們需要刪除⾥⾯的 5 :

⾸先需要判斷鏈表頭結點是不是為空，如果為空，那麼就直接返回NULL ，如果等於我們要找的，那麼直接返回下⼀個節點引⽤即可。

如果不符合以上説的，那麼我們需要新建⼀個前置節點pre ,與現在的鏈表連接在⼀起：

然後初始化⼀個 cur 節點表示當前節點，指向 head 節點：

cur 不為空， cur 和 pre 後移：

發現 cur 正是我們需要查找的 5 ，那麼記錄下 5 的下⼀個節點 1 ,也就是next :

cur 的 next 指向 NULL ,使⽤ pre 的 next 指向剛剛記錄的 next :

簡化鏈表也就是：

取之前虛擬的頭結點的後⼀個節點，就是刪除掉之後的新鏈表：

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
    	this.val = val;
	}
}

public class Solution13 {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
        	return null;
        }
        
        if (head.val == val) {
        	return head.next;
        }
        
        // ⽤⼀個節點將頭結點鏈接起來
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            if (cur.val == val) {
                // 將前置節點直接連接後⼀個節點，相當於刪除掉了該節點
                pre.next = cur.next;
                break;
            }
            cur = cur.next;
            pre = pre.next;
        }
        return head;
    }
}

迭代

通過遍歷鏈表找到目標節點並修改指針，維護前驅指針，當找到目標節點時修改指針跳過該節點

public class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        // 處理頭節點就是要刪除的節點的情況
        if (head != null && head.val == val) {
            return head.next;
        }
        
        ListNode prev = null;
        ListNode curr = head;
        
        // 遍歷查找目標節點
        while (curr != null && curr.val != val) {
            prev = curr;
            curr = curr.next;
        }
        
        // 找到目標節點後跳過它
        if (curr != null) {
            prev.next = curr.next;
        }
        
        return head;
    }
}

• 時間複雜度：O(n)，最壞情況下需要遍歷整個鏈表
• 空間複雜度：O(1)，只使用常數空間

遞歸

當前節點是要刪除的節點則返回next，否則遞歸處理剩餘鏈表

public class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        // 遞歸終止條件
        if (head == null) {
            return null;
        }
        
        // 當前節點是要刪除的節點
        if (head.val == val) {
            return head.next;
        }
        
        // 遞歸處理剩餘鏈表
        head.next = deleteNode(head.next, val);
        return head;
    }
}

• 時間複雜度：O(n)，需要處理每個節點
• 空間複雜度：O(n)，遞歸調用棧的深度