[LeetCode]203. 移除链表元素

203. 移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解法1

class Solution:
    def removeElements(self, head, val):
        if head:
            while head.val == val:  #遇到需要删除的元素
                head = head.next    #直接指向下一个元素
                if head is None:    #链表尾节点直接return
                    return head
            q = head    #当前
            p = q.next  #后继
            while p:    #后继不为空
                if p.val == val:    #后继需要删除
                    q.next = p.next #当前的next指向后继的next
                else:
                    q = q.next
                p = p.next
        return head

解法2

class Solution:
    def removeElements(self, head, val):
        L = pre = ListNode(0)
        pre.next = head
        p = head      
        
        while p :
            if p.val == val:
                pre.next = p.next
                del(p)
                p = pre.next
            else:
                pre = pre.next
                p = p.next  
        return L.next

解法3

class Solution:
    def removeElements(self, head, val):
        dummy_head = ListNode(-1)
        dummy_head.next = head
        
        prev = dummy_head
        while prev.next is not None:
            if prev.next.val == val:
                prev.next = prev.next.next
            else:
                prev = prev.next
                
        return dummy_head.next

解法4

递归求解:

class Solution:
    def removeElements(self, head, val):
        if head is None:
            return None
        head.next = self.removeElements(head.next, val)
        return head.next if head.val == val else head