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

hzc 發布于2019-08-16 18:37 / 2782人閱讀

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

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

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

解題思路：

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

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

迭代法：

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

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

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

Java：

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

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

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

遞歸法：

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

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

直到回到第一個遞歸函數為止返回頭節點結束。

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

歡迎關注公眾號一起學習：愛寫Bug

云服務器 GPU云服務器移除元素移除數組元素 js 數據移除元素 js數組如何移除元素

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

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

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

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

makeFoxPlay 2019-07-31 11:28 評論0 收藏0
LeetCode【203】：移除鏈表元素

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

wwolf 2019-08-19 11:38 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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

warmcheng 2019-08-26 10:09 評論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 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論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 2019-07-25 12:04 評論0 收藏0