[[436875]]

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

 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é)點(diǎn)

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

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

示例 2:

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

解題思路：

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

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

** 算法流程：**

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

復(fù)雜度分析：

• 時(shí)間復(fù)雜度 O(N)： N為鏈表長(zhǎng)度，刪除操作平均需循環(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 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 刪除鏈表的節(jié)點(diǎn) 
 */ 
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é)點(diǎn)是末尾節(jié)點(diǎn)，往后移一個(gè) 
            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; 
            } 
        } 
    } 
 
    /** 
     * 單指針實(shí)現(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; 
    } 
 
    /** 
     * 遞歸實(shí)現(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