【leetcode】链表203

题目详情

题目分析

需要两个链表指针，一个指向头结点的dummy节点，一个记录head节点的prev节点
遍历链表，当head.val == val时删除
删除的方法：prev.next = pre.next.next

迭代法

时间复杂度：O(N)
空间复杂度：O(1)

C++实现

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode drummy ;  //指向链表的头部
        drummy.next = head;
        //记录移动的头部的上个节点
        ListNode prev = drummy;
        while ( head != NULL)
        {
            if( head->val == val)
            {
                prev.next = head->next;
            }
            else
            {
                head = &prev;    
            }
            head=head->next;  //迭代的实现
        }
        return drummy.next;

    }
};

python实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
       
        drummy = ListNode()
        drummy.next =head
        prev =drummy
        while  head != None:
            if head.val == val:
                prev.next = head.next  
            else:
                prev =head
            head = head.next
        return drummy.next

递归法

链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解
递归的终止条件是 head 为空，此时直接返回 head。
当 head 不为空时，递归地进行删除 *** 作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。
时间复杂度：O(N)
空间复杂度：O(N)

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) {
            return head;
        }
        head->next = removeElements(head->next, val); //一直递归判断是否符合三目运算符
        return head->val == val ? head->next : head;  //三目运算符
    }
};