203. 移除链表元素

题目

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

示例一

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

示例二

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

示例三

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

思路

方法1-1：设置哑节点(dummy)，然后直接迭代

哑节点是一个虚拟的头节点，在这一题里面，头节点是可能被删除的，删除后的头节点还要考虑需不需要删除；或者当指针往后迭代的过程中，头节点就找不到了，没办法之间返回头节点，这个时候设置哑节点可以有效的解决这些麻烦。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        vhead = ListNode(-1,head)#设置哑节点
        p = vhead#这是移动指针，指向当前要处理的节点
        if p == None: return None
        while p.next != None:
            if (p.next).val == val:
                p.next = (p.next).next
            else:
                p = p.next
        return vhead.next

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

方法1-2：还是设置哑节点+双指针

和方法1-1没啥区别，个人感觉双指针直观上好理解一点。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        vhead = ListNode(-1,head)
        left = vhead
        right = head
        if vhead.next == None: return None
        while right != None:
            if right.val == val:
                left.next = right.next
                right = right.next
            else:
                left = right
                right = right.next
        return vhead.next

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

方法2：递归

**参考了评论区的大佬的思路。**迭代的方法要稍微理解一下，简单来说，对头节点以外的节点进行删除val的操作。递归的中止调节是头节点为空。

**我个人理解：**对链表从前往后看就是把当前节点和后续已经删除了val的链表相连，从后往前看就是链表从后往前删除有val值的节点。

官方的解答文字：链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点，可以用递归实现。

对于给定的链表，首先对除了头节点head以外的节点进行删除操作，然后判断head的节点值是否等于给定的val。如果head的节点值等于val，则head需要被删除，因此删除操作后的头节点为head.next；如果head 的节点值不等于val，则head保留，因此删除操作后的头节点还是head。上述过程是一个递归的过程。

递归的终止条件是head为空，此时直接返回head。当head不为空时，递归地进行删除操作，然后判断head的节点值是否等于val并决定是否要删除head。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if head == None:
            return head
        head.next = self.removeElements(head.next,val)
        if head.val == val:
            return head.next
        else:
            return head