LeetCode 203：移除鏈表元素 Remove LinkedList Elements

hzc 發(fā)布于2019-08-16 18:37 / 2805人閱讀

摘要：刪除鏈表中等于給定值的所有節(jié)點(diǎn)。鏈表的刪除操作是直接將刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)指向刪除節(jié)點(diǎn)的后一個節(jié)點(diǎn)即可。這就無需考慮頭節(jié)點(diǎn)是否為空是否為待刪除節(jié)點(diǎn)。

刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)。

Remove all elements from a linked list of integers that have value val.

示例:

輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5

解題思路：

兩種方法，一種是迭代法，從第一個節(jié)點(diǎn)開始，遇到值相同的節(jié)點(diǎn)就將其刪除。鏈表的刪除操作是直接將刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)指向刪除節(jié)點(diǎn)的后一個節(jié)點(diǎn)即可。

第二種方法是遞歸，用遞歸從后向前遇到相同節(jié)點(diǎn)直接指向該節(jié)點(diǎn)的下一個節(jié)點(diǎn)的地址即可

迭代法：

由于鏈表刪除操作的特殊性，如果要刪除某個節(jié)點(diǎn)，必須要知道該刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)地址才可完成刪除操作。所以如果是從第一個節(jié)點(diǎn)開始判斷，就要考慮到第一個節(jié)點(diǎn)是否為空節(jié)點(diǎn)、第一個節(jié)點(diǎn)是否就是該刪除的的節(jié)點(diǎn)，刪除頭節(jié)點(diǎn)和非頭節(jié)點(diǎn)的操作不一樣，應(yīng)多帶帶實(shí)現(xiàn)刪除操作。

如果原鏈表是這種形式：1->1->1->2 val=1 刪除頭節(jié)點(diǎn)后第二個節(jié)點(diǎn)置為頭節(jié)點(diǎn)，但是第二個節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)依然需要刪除，所以對頭節(jié)點(diǎn)的操作應(yīng)該是一個迭代過程。

另外一種方法就是新建一個虛擬節(jié)點(diǎn)，該虛擬節(jié)點(diǎn)下一個節(jié)點(diǎn)指向原鏈表頭節(jié)點(diǎn)。這就無需考慮頭節(jié)點(diǎn)是否為空、是否為待刪除節(jié)點(diǎn)。如原鏈表為：1->1->1->2 val=1 ，新建一個虛擬節(jié)點(diǎn) -1 作為頭節(jié)點(diǎn)：-1->1->1->1->2 val=1 ，這時(shí)只需正常迭代刪除即可，唯一要注意是返回節(jié)點(diǎn)不能是 head ，因?yàn)樵湵淼念^節(jié)點(diǎn)如果是待刪除節(jié)點(diǎn)，此時(shí) head 節(jié)點(diǎn)已被刪除并作為多帶帶隔離出來的節(jié)點(diǎn)，并非鏈表內(nèi)的一個節(jié)點(diǎn)。

Java：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode newHead=new ListNode(-1);//新建虛擬節(jié)點(diǎn)
        newHead.next=head;//虛擬節(jié)點(diǎn)作為原鏈表的頭節(jié)點(diǎn)
        ListNode cur = newHead;//遍歷節(jié)點(diǎn)的指針

        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;//刪除操作
            } else {
                cur = cur.next;
            }
        }
        return newHead.next;//返回的頭節(jié)點(diǎn)應(yīng)當(dāng)是虛擬節(jié)點(diǎn)的下一個節(jié)點(diǎn)
    }
}

Python3：

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        newHead = ListNode(-1)
        newHead.next = head
        cur = newHead
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return newHead.next

遞歸法：

遞歸方法解該題很簡單，基線條件是遇到空節(jié)點(diǎn)（最后一個節(jié)點(diǎn)），遞歸時(shí)只需將傳遞參數(shù)節(jié)點(diǎn)的下一個節(jié)點(diǎn)作為新的參數(shù)傳給遞歸函數(shù)即可：

如原鏈表為： 1->2->6->3->4->5->6, val = 6
遞歸到空節(jié)點(diǎn)時(shí)最后一個遞歸函數(shù)返回null： 1->2->6->3->4->5->6->null
回到上一層遞歸函數(shù)內(nèi)此時(shí) head.next 得到返回節(jié)點(diǎn) null
判斷head為 6 刪除，返回 head.next ：1->2->6->3->4->5->null
回到上一層遞歸函數(shù)此時(shí) head.next 得到上一層返回節(jié)點(diǎn)依然為null
判斷head為 5 不刪除，返回 head 為5：1->2->6->3->4->5->null
回到上一層遞歸函數(shù)此時(shí) head.next 得到上一層返回節(jié)點(diǎn) 5
判斷head為 4 不刪除，返回 head 為4：1->2->6->3->4->5->null
回到上一層遞歸函數(shù)此時(shí) head.next 得到上一層返回節(jié)點(diǎn) 4
..............

直到回到第一個遞歸函數(shù)為止返回頭節(jié)點(diǎn)結(jié)束。

Java：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;//基線條件
        head.next = removeElements(head.next, val);
        if (head.val == val) {
            return head.next;
        } else {
            return head;
        }
    }
}

Python3：

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head: return None
        head.next = self.removeElements(head.next, val)
        if head.val == val:
            return head.next
        else:
            return head

歡迎關(guān)注公眾號一起學(xué)習(xí)：愛寫B(tài)ug

云服務(wù)器 GPU云服務(wù)器移除元素移除數(shù)組元素 js 數(shù)據(jù)移除元素 js數(shù)組如何移除元素

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75446.html

發(fā)表評論

登陸后可評論

0條評論

hzc

男|高級講師

我要關(guān)注我要私信

TA的文章

卸載tensorflow

閱讀 1191·2023-04-25 14:35
python入門 django入門（一）

閱讀 2867·2021-11-16 11:45
UnixBench：Linux VPS 服務(wù)器性能測試跑分腳本

閱讀 3473·2021-09-04 16:48
NexusBytes：$26.88/年/AMD Ryzen/1GB內(nèi)存/20GB NVMe空間/30

閱讀 2211·2021-08-10 09:43
分享一個移動端滑到底部翻頁的代碼

閱讀 557·2019-08-30 13:17
IOING在開發(fā)SPA大型應(yīng)用時(shí)有哪些必要的技術(shù)條件？

閱讀 1658·2019-08-29 13:27
數(shù)組截?cái)嗨惴ǎ↗avaScript）

閱讀 930·2019-08-26 13:58
JavaScript 關(guān)于ES6 const 深入理解

閱讀 2185·2019-08-26 13:48

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

LeetCode 203：移除鏈表元素 Remove LinkedList Elements

相關(guān)文章