[[436875]]

本文轉(zhuǎn)載自微信公眾號「程序員千羽」，作者程序員千羽。轉(zhuǎn)載本文請聯(lián)系J程序員千羽公眾號。

 Leetcode : https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof

“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_12_hammingWeight/Solution.java

刪除鏈表的節(jié)點

“題目描述： 給定單向鏈表的頭指針和一個要刪除的節(jié)點的值，定義一個函數(shù)刪除該節(jié)點。返回刪除后的鏈表的頭節(jié)點。示例 1:

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

示例 2:

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

解題思路：

本題刪除值為 val 的節(jié)點分需為兩步：定位節(jié)點、修改引用。

• 定位節(jié)點： 遍歷鏈表，直到 head.val == val 時跳出，即可定位目標節(jié)點。
• 修改引用： 設(shè)節(jié)點 cur 的前驅(qū)節(jié)點為 pre ，后繼節(jié)點為 cur.next ;則執(zhí)行 pre.next = cur.next ，即可實現(xiàn)刪除 cur 節(jié)點。

** 算法流程：**

• 特例處理： 當應(yīng)刪除頭節(jié)點 head 時，直接返回 head.next 即可。
• 初始化： pre = head , cur = head.next 。
• 定位節(jié)點： 當 cur 為空 或 cur 節(jié)點值等于 val 時跳出。
  • 保存當前節(jié)點索引，即 pre = cur 。
  • 遍歷下一節(jié)點，即 cur = cur.next 。
• 刪除節(jié)點： 若 cur 指向某節(jié)點，則執(zhí)行 pre.next = cur.next ;若 cur 指向 nullnull ，代表鏈表中不包含值為 val 的節(jié)點。
• 返回值： 返回鏈表頭部節(jié)點 head 即可。

復(fù)雜度分析：

• 時間復(fù)雜度 O(N)： N為鏈表長度，刪除操作平均需循環(huán) N/2 次，最差 N 次。
• 空間復(fù)雜度 O(1) ： cur, pre 占用常數(shù)大小額外空間。

package com.nateshao.sword_offer.topic_15_deleteNode; 
 
/** 
 * @date Created by 邵桐杰 on 2021/11/21 16:22 
 * @微信公眾號 程序員千羽 
 * @個人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 刪除鏈表的節(jié)點 
 */ 
public class Solution { 
    public static void main(String[] args) { 
        ListNode listNode = new ListNode(3); 
        int val = 3; 
        ListNode node = deleteNode(listNode, val); 
        System.out.println("node = " + node); 
    } 
 // 推薦 
    public static ListNode deleteNode(ListNode head, int val) { 
        if (head.val == val) return head.next; 
        ListNode pre = head, cur = head.next; 
        while (cur != null && cur.val != val) { 
            pre = cur; 
            cur = cur.next; 
        } 
        if (cur != null) pre.next = cur.next; 
        return head; 
    } 
 
    public void deleteNode(ListNode head, ListNode deListNode) { 
        if (deListNode == null || head == null) 
            return; 
        if (head == deListNode) { 
            head = null; 
        } else { 
            // 若刪除節(jié)點是末尾節(jié)點，往后移一個 
            if (deListNode.next == null) { 
                ListNode pointListNode = head; 
                while (pointListNode.next.next != null) { 
                    pointListNode = pointListNode.next; 
                } 
                pointListNode.next = null; 
            } else { 
                deListNode.val = deListNode.next.val; 
                deListNode.next = deListNode.next.next; 
            } 
        } 
    } 
 
    /** 
     * 單指針實現(xiàn) 
     * 
     * @param head 
     * @param val 
     * @return 
     */ 
    public ListNode deleteNode2(ListNode head, int val) { 
        if (head == null) return null; 
        if (head.val == val) return head.next; 
        ListNode cur = head; 
        while (cur.next != null && cur.next.val != val) { 
            cur = cur.next; 
        } 
        if (cur.next != null) { 
            cur.next = cur.next.next; 
        } 
        return head; 
    } 
 
    /** 
     * 遞歸實現(xiàn) 
     * 
     * @param head 
     * @param val 
     * @return 
     */ 
    public ListNode deleteNode3(ListNode head, int val) { 
        if (head == null) return null; 
        if (head.val == val) return head.next; 
        else head.next = deleteNode3(head.next, val); 
        return head; 
    } 
 
    public static class ListNode { 
        int val; 
        ListNode next; 
 
        ListNode(int x) { 
            val = x; 
        } 
    } 
} 

參考鏈接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/mian-shi-ti-18-shan-chu-lian-biao-de-jie-dian-sh-2