虚拟头结点法

在头节点需要进行判断时，可以使用虚拟头节点，此时虚拟节点的next指向头结点。虚拟头结点在许多题目中都可以采用。

题目描述：

移除链表元素（力扣链接🔗）

题目分析：

删除节点的思路：

此时头结点需要判断，所以右两种方法：

• 直接使用原来的链表来进行删除操作。
• 设置一个虚拟头结点在进行删除操作。

解法一：

在原来的链表删除。

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

代码：

不添加虚拟节点方式

时间复杂度 O(n) ， 空间复杂度 O(1)

public ListNode removeElements(ListNode head, int val) {
    // 不使用虚拟的头节点的方法
    // 先将前面相等的移除，也就是移除头结点
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为空，提前退出
    if (head == null) {
        return head;
    }
    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。注意最后返回虚拟头节点的next。

代码：

public ListNode removeElements(ListNode head, int val) {
    // 为空直接返回
    if (head == null) {
        return head;
    }
    ListNode dummy = new ListNode(-1, head);    // 虚拟头结点
    ListNode pre = dummy;
    ListNode cur = dummy.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            // 移动前指针到后指针的位置
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
    }
}

其他虚拟头结点案例

两两交换链表中的节点（🔗）