|
來(lái)源：LeetCode第203題 難度：簡(jiǎn)單 給你一個(gè)鏈表的頭節(jié)點(diǎn)head和一個(gè)整數(shù)val，請(qǐng)你刪除鏈表中所有滿足Node.val==val的節(jié)點(diǎn)，并返回新的頭節(jié)點(diǎn)。 示例 1： 
輸入：head = [1,2,6,3,4,5,6], val = 6 輸出：[1,2,3,4,5]
示例 2： 輸入：head = [], val = 1 輸出：[]
示例 3：
輸入：head = [7,7,7,7], val = 7 輸出：[]
提示： 這題讓刪除節(jié)點(diǎn)值等于val的節(jié)點(diǎn)，一種常見(jiàn)的方式就是逐個(gè)節(jié)點(diǎn)判斷。但如果head節(jié)點(diǎn)的值等于val的時(shí)候，我們可能會(huì)把鏈表搞丟，一種最常見(jiàn)的方式就是創(chuàng)建一個(gè)dummy節(jié)點(diǎn)，讓他指向head節(jié)點(diǎn)。原理比較簡(jiǎn)單，我們來(lái)看個(gè)動(dòng)畫
最后再來(lái)看下代碼
public ListNode removeElements(ListNode head, int val) {
//創(chuàng)建一個(gè)啞結(jié)點(diǎn)
ListNode dummy = new ListNode(0);
dummy.next = head;
//前一個(gè)節(jié)點(diǎn)pre
ListNode pre = dummy;
while (pre.next != null) {
//如果pre.next節(jié)點(diǎn)值等于val，就把pre.next節(jié)點(diǎn)給刪除
if (pre.next.val == val)
pre.next = pre.next.next;
else
pre = pre.next;
}
return dummy.next;
}
這個(gè)可以參考595，刪除排序鏈表中的重復(fù)元素，我們可以使用尾遞歸的方式，當(dāng)遞歸往回走的時(shí)候在進(jìn)行判斷刪除，代碼如下 public ListNode removeElements(ListNode head, int val) {
//如果為空，直接返回
if (head == null)
return head;
//先刪除當(dāng)前節(jié)點(diǎn)后面需要?jiǎng)h除的節(jié)點(diǎn)
ListNode next = removeElements(head.next, val);
//如果當(dāng)前節(jié)點(diǎn)的值等于val，我們直接返回next
if (head.val == val)
return next;
//返回head節(jié)點(diǎn)，注意原來(lái)head的next節(jié)點(diǎn)可能改變，
//所以這里要重新賦值
head.next = next;
return head;
}
當(dāng)然也可以改為首遞歸的方式，就是先判斷刪除，然后在遞歸調(diào)用
public ListNode removeElements(ListNode head, int val) {
//如果為空，直接返回
if (head == null)
return head;
//先刪除
while (head != null && head.val == val)
head = head.next;
if (head == null)
return null;
//遞歸
head.next = removeElements(head.next, val);
return head;
}
|
