LeetCode【203】：移除鏈表元素

wwolf 發布于2019-08-19 11:38 / 3493人閱讀

摘要：題目描述刪除鏈表中等于給定值的所有節點。示例輸入輸出非遞歸解法思路遍歷鏈表，找出每個待刪除節點的前一個節點。特殊情況第一個節點就是待刪除節點時，要多帶帶操作。注意點當輸入為時，按上面的思路刪除第一個節點，剩下的鏈表的頭節點又是待刪除節點。

題目描述

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

示例

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

非遞歸解法 思路

遍歷鏈表，找出每個待刪除節點的前一個節點。
特殊情況：第一個節點就是待刪除節點時，要多帶帶操作。
注意點：當輸入為：[1,1]時，按上面的思路刪除第一個節點，剩下的鏈表的頭節點又是待刪除節點。

    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            ListNode pre = head;
            head = pre.next;
            pre.next = null;
        }
            
        if(head == null){
            return null;
        }
        ListNode pre = head;
        while(pre.next!=null){
            ListNode cur = pre.next;
            if(cur.val == val){
            pre.next = cur.next;
            cur.next = null;
            }else{
                pre = pre.next;
            }    
        }
        return head;
        
    }

使用虛擬頭結點（統一頭節點和其他節點的操作）簡化代碼:

    private class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        while(pre.next!=null){
            ListNode del = pre.next;
            if(del.val == val){
            pre.next = del.next;
            del.next = null;
            }else{
                pre = pre.next;
            }
                
        }
        return dummyHead.next;
        
    }

注意：這里返回時不能直接return head;

測試用例：

    public class ListNode {

    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
    }

    // 鏈表節點的構造函數
    // 使用arr為參數，創建一個鏈表，當前的ListNode為鏈表頭結點
    public ListNode(int[] arr){

        if(arr == null || arr.length == 0)
            throw new IllegalArgumentException("arr can not be empty");

        this.val = arr[0];
        ListNode cur = this;
        for(int i = 1 ; i < arr.length ; i ++){
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    // 以當前節點為頭結點的鏈表信息字符串
    @Override
    public String toString(){

        StringBuilder s = new StringBuilder();
        ListNode cur = this;
        while(cur != null){
            s.append(cur.val + "->");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}

遞歸解法

    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;
        }        
    }

參考：《玩轉數據結構》

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77602.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-...

hzc 2019-08-16 18:37 評論0 收藏0
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
移除鏈表倒數第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
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