【算法|虚拟头节点|链表】移除链表元素

Leetcode203

移除链表元素

题目描述：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
1
2

示例 2：

输入：head = [], val = 1
输出：[]
1
2

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]
1
2

原链表操作

如果我们选择在原链表上进行操作的话，我们需要考虑两个方面的问题：

1. 头节点为我们要移除的元素
2. 非头结点为我们要移除的元素

Java版本

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //处理头节点
        while(head != null && head.val == val){
            head = head.next;
        } 
        //处理头节点为空的情况
        if(head == null){
            return head;
        }
        //确保head.val != val 的情况
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            head = head.next;
        }
        ListNode cur = head;
        while(cur != null){
            while(cur.next != null && cur.next.val == val){
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

C++版本

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //删除头节点
        while(head != NULL && head->val == val){
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }
        //删除非头结点
        ListNode* cur = head;
        while(cur != NULL && cur->next != NULL){
            if(cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }else{
                cur = cur->next;
            }
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

虚拟头节点

介绍

虚拟头节点是一种在链表中使用的特殊节点，它通常作为头节点的前一个节点，但是不存储具体的数据。它的目的是为了简化链表的操作，特别是在处理边界条件和插入、删除操作时提供便利。

在传统的链表实现中，如果要对链表进行插入或者删除操作，我们需要分别处理头节点的情况和中间节点的情况。这样就需要额外的代码来处理这些边界情况，增加了代码的复杂度。

而使用虚拟头节点，我们可以将这些特殊情况都统一为对中间节点的操作。具体来说，虚拟头节点就像是链表中的一个普通节点，但是它不存储具体的数据。当链表为空时，虚拟头节点就是唯一的节点，它的下一个节点就是链表的真正的头节点。当链表非空时，虚拟头节点的下一个节点就是链表的真正的头节点。

插入操作时，我们只需要将新节点插入到虚拟头节点的后面即可，而不需要单独处理头节点为空的情况。删除操作时，我们只需要将虚拟头节点的后继节点指向要删除的节点的后继节点即可，而不需要单独处理删除头节点的情况。

使用虚拟头节点的好处是简化了链表的操作逻辑和代码，让代码更加简洁和可读。同时，它也保证了链表的头节点和其他节点的统一性，避免了对头节点的特殊处理。

总结起来，虚拟头节点是一个不存储具体数据的特殊节点，它位于真正的头节点之前，用于简化链表的操作和处理边界情况。它统一了对头节点和其他节点的操作，使得代码更加简洁和可维护

所以当我们在原链表操作时，我们需要针对每一种情况去编写逻辑，但使用虚拟头结点的话，就可以统一移除节点这一操作~

Java版本

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;

        while(pre.next != null){
            if(pre.next.val == val){
                pre.next = pre.next.next;
            }else{
                pre = pre.next;
            }
        }
        return dummyHead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16