美文网首页
*【链表】203.移除链表元素

*【链表】203.移除链表元素

作者: ___Qian___ | 来源:发表于2019-01-15 10:08 被阅读0次

    题目

    删除链表中等于给定值 val 的所有节点。

    示例:

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

    思路

    1. 在链表中删除节点要将cur指针指向待删除节点的前一个节点。
      因此每次判断cur的下一个节点值是否等于val。
      但是这个逻辑不能判断链表的第一个节点,需要对第一个节点做特殊处理,具体见代码,注意这种方法有很多陷阱,有很多特殊情况做好判断。
    // 不使用虚拟头结点
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    
    
        public ListNode removeElements(ListNode head, int val) {
    
            // 需要对头结点进行特殊处理
            while(head != null && head.val == val){
                ListNode node = head;
                head = head.next;
            }
    
            if(head == null)
                return head;
    
            ListNode cur = head;
            while(cur.next != null){
                if(cur.next.val == val){
                    ListNode delNode = cur.next;
                    cur.next = delNode.next;
                }
                else
                    cur = cur.next;
            }
    
            return head;
        }
    
    
    1. 上面的方法因为第一个节点的特殊性,使得代码逻辑不太清晰。
      处理链表的一个重要技巧是设立虚拟头结点,初始cur指向虚拟头结点,这样就能判断到链表中的所有节点。
    public ListNode removeElements(ListNode head, int val) {
    
            // 创建虚拟头结点
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
    
            ListNode cur = dummyHead;
            while(cur.next != null){
                if(cur.next.val == val ){
                    ListNode delNode = cur.next;
                    cur.next = delNode.next;
                }
                else
                    cur = cur.next;
            }
    
            return dummyHead.next;
        }
    

    相关文章

      网友评论

          本文标题:*【链表】203.移除链表元素

          本文链接:https://www.haomeiwen.com/subject/iieedqtx.html