Leetcode 203: Remove Linked List Elements

问题描述:
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
去掉单链表中=val的节点

思路:
因为是单链表,一般来讲重构链表操作需要用到两个指针,而且两个指针位置错开才有意义。比如说这道题,如果指针iter探察到了当下这个节点该删,这时候必须有一个该节点之前的指针用来定位。我设计的方法是当iter探察到某一个该删的节点时,iter主动向前跳一格(做个比喻:把要删的节点比作一条河,last和iter两个人分别站在河的两岸),last把next定在iter上,就等同于将该删的节点摘链了。如此重复,而且对于删除尾节点有效。

另外值得注意的:
(1)为了避免head不存在的麻烦,我们在head之前连接一个辅助节点dummy_head(假头)。我们返回的时候可以放心地返回dummy_head.next 。无非是以下三种情况,“假头”都会方便我们编程。情况一:假头.next是我们原来的真头;情况二:假头.next不是原来的真头(真头可能被删了);情况三:所有的节点全被删了,假头.next指向null
(2) while循环中的循环条件 while(iter!=null), 这样设定比较好,因为这样可以保证iter可以指完所有的节点。对比iter.next!=null容易使循环卡在最后一个节点上.

代码如下:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head==null) return null;
        ListNode dummy_head = new ListNode(-1);
        dummy_head.next = head;
        ListNode iter = head;
        ListNode last = dummy_head;
        while(iter!=null){
            if (iter.val==val){
                iter=iter.next;
                last.next.next=null;
                last.next = iter;
            }
            else{
                iter=iter.next;
                last=last.next;
            }
        }
        return dummy_head.next;
    }
}

时间复杂度: O(n)

上一篇:Flutter - 手写体widgets之wired_elements


下一篇:微信公众号,统计公众平台的打赏人数和金额脚本