移除链表元素

学习文本来源：代码随想录

力扣地址

题意：删除链表中等于给定值val的所有节点

示例1：

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

示例2:

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

示例3：

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

思路

这里以链表 1->4->2->4 来举例，移除元素4。得出1->2

那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？

这里涉及如下链表操作的两种方式：

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

来看第一种操作：直接使用原来的链表来进行移除。

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

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

这样移除了一个头结点，是不是发现，在单链表中移除头结点和移除其他节点的操作方式不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。

那么可不可以以一种统一的逻辑来移除链表节点呢。

其实可以设置一个虚拟头结点，这样原链表的所有节点都可以按照统一的方式进行移除可。

来看看如何设置一个虚拟头。依然还是在这个链表中移除1.

这里来个链表加个虚拟头结点为新的头节点，此时要移除这个旧头结点元素1.

这样是不是可以使用移除其他节点的方式统一了呢？

来看一下，如何移除元素1呢，还是熟悉的方式。

最后呢子啊题目中return的时候别忘记return dummy->next，这才是新的头结点

直接使用原来的链表来进行移除节点操作：
golang:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    now := head
    if head == nil { return head }
    for now.Next != nil {
        if now.Next.Val == val {
            now.Next = now.Next.Next
        } else {
            now = now.Next
        }
    }
    if head.Val == val {
        head = head.Next
    }
    return head
}

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

设置一个虚拟头结点在进行移除操作：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    newHead := &ListNode{0,head}
    now := newHead
    for now.Next != nil {
        if now.Next.Val == val {
            now.Next = now.Next.Next
        } else {
            now = now.Next
        }
    }
    return newHead.Next
}

链表-移除链表元素