问题描述:
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)