国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

makeFoxPlay / 2801人閱讀

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

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

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é)點開始,遇到值相同的節(jié)點就將其刪除。鏈表的刪除操作是直接將刪除節(jié)點的前一個節(jié)點指向刪除節(jié)點的后一個節(jié)點即可。

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

迭代法:

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

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

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

Java:

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

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

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é)點(最后一個節(jié)點),遞歸時只需將傳遞參數節(jié)點的下一個節(jié)點作為新的參數傳給遞歸函數即可:

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

直到回到第一個遞歸函數為止返回頭節(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
歡迎關注公眾號一起學習:愛寫B(tài)ug

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

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/45178.html

相關文章

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

    摘要:刪除鏈表中等于給定值的所有節(jié)點。鏈表的刪除操作是直接將刪除節(jié)點的前一個節(jié)點指向刪除節(jié)點的后一個節(jié)點即可。這就無需考慮頭節(jié)點是否為空是否為待刪除節(jié)點。 刪除鏈表中等于給定值 val 的所有節(jié)點。 Remove all elements from a linked list of integers that have value val. 示例: 輸入: 1->2->6->3->4->5-...

    hzc 評論0 收藏0
  • LeetCode203】:移除鏈表元素

    摘要:題目描述刪除鏈表中等于給定值的所有節(jié)點。示例輸入輸出非遞歸解法思路遍歷鏈表,找出每個待刪除節(jié)點的前一個節(jié)點。特殊情況第一個節(jié)點就是待刪除節(jié)點時,要單獨操作。注意點當輸入為時,按上面的思路刪除第一個節(jié)點,剩下的鏈表的頭節(jié)點又是待刪除節(jié)點。 題目描述 刪除鏈表中等于給定值 val 的所有節(jié)點。 示例 輸入: 1->2->6->3->4->5->6, val = 6輸出: 1->2->3->...

    wwolf 評論0 收藏0
  • LeetCode 攻略 - 2019 年 7 月上半月匯總(55 題攻略)

    摘要:微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容,進行補充,并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評論0 收藏0
  • LeetCode 攻略 - 2019 年 7 月下半月匯總(100 題攻略)

    摘要:月下半旬攻略道題,目前已攻略題。目前簡單難度攻略已經到題,所以后面會調整自己,在刷算法與數據結構的同時,攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區(qū)別...

    tain335 評論0 收藏0
  • 移除鏈表倒數第n個元素

    摘要:移除鏈表倒數第個元素給定一個鏈表,移除倒數第個元素,返回鏈表頭部。 移除鏈表倒數第n個元素 Remove Nth Node From End of List 給定一個鏈表,移除倒數第n個元素,返回鏈表頭部。 Given a linked list, remove the nth node from the end of list and return its head. Note:...

    yhaolpz 評論0 收藏0

發(fā)表評論

0條評論

makeFoxPlay

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<