526互联

移除链表元素

发布时间 2023-03-22 21:12:59作者: Coeleone

移除链表元素

移除一个链表中的指定元素，这里给出三种方法，新建链表、迭代、递归

对应题目203. 移除链表元素?

新建链表

首先创建一个新的链表，再遍历需要进行移除元素的链表。如果遇到与目标元素值不相等的情况，那么新建一个节点然后把值传给这个节点。逐一操作最后得到一个新的链表，那么这个链表当中就不包括目标元素，完成移除的操作。分析复杂度，由于需要遍历每个节点因此其时间复杂度为\(O(N)\)，同样的需要创建一个新表，那么空间复杂度为\(O(N).\)

ListNode* removeElements(ListNode* head, int val) {
    	// define a new List to store the val of head which isn't equle to "val".
        ListNode* result = new ListNode();
        ListNode* p = result;
        while(head != nullptr) {
            if(head->val != val) {
                p->next = new ListNode(head->val);
                p = p->next;
            }
            head = head->next;
        }
        return result->next;
}

迭代

传统删除链表的方法，需要注意链表是否带头结点，如果不带头结点可以定义一个虚拟的头结点方便操作。这里的难点就在于不带头结点时，删除第一个节点的方法，所以定义一个dummyHead方便后续操作。分析复杂度，由于需要遍历所有的节点，所以时间复杂独卫\(O(N)\)，对于空间复杂度，简单分析得到为\(O(1)\)。

ListNode* removeElements(ListNode* head, int val) {
    	//determine whether the linkList is empty.if yes,then return a null pointer.
        if (head == nullptr)
            return nullptr;
    	//define a dummy head node so as to operation.
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode* p = dummyHead;
        while(p->next != nullptr) {
            if(p->next->val == val) {
                p->next = p->next->next;
            }else{
                p = p->next;
            }
        }
        return dummyHead->next;
}

递归

链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。删除链表中所有节点值等于特定值的节点，可以用递归实现。分析复杂度，时间复杂度由于需要递归所有的节点所以其复杂度为\(O(N)\)，空间复杂度，需要使用栈空间同样为\(O(N)\)。

ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr)
            return head;
        head->next = removeElements(head->next,val);
        return head->val == val ? head->next : head;
}