题目
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
思路
- 在链表中删除节点要将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;
}
- 上面的方法因为第一个节点的特殊性，使得代码逻辑不太清晰。
处理链表的一个重要技巧是设立虚拟头结点，初始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;
}
