【問(wèn)題描述】[中等]

給定單向鏈表的頭指針和一個(gè)要?jiǎng)h除的節(jié)點(diǎn)的值，定義一個(gè)函數(shù)刪除該節(jié)點(diǎn)。返回刪除后的鏈表的頭節(jié)點(diǎn)。注意：此題對(duì)比原題有改動(dòng)示例 1:輸入: head = [4,5,1,9], val = 5 輸出: [4,1,9] 解釋: 給定你鏈表中值為 5 的第二個(gè)節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.

【解答思路】

1. 雙指針

時(shí)間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(1)

class Solution {public 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;} }

2.單指針

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

public ListNode deleteNode(ListNode head, int val) {if(head.val == val) return head.next;ListNode cur = head;while(cur != null){if(cur.next.val == val ){cur.next = cur.next.next;break;}cur=cur.next;}return head;}

【總結(jié)】

1.畫(huà)圖理解指針問(wèn)題

2.遍歷指針

ListNode cur = head;while(cur != null)cur=cur.next;}

3.鏈表為空作判斷 鏈表頭尾特殊判斷

參考鏈接：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/

總結(jié)

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[18]题[删除链表的节点]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。