Subject to introduce

Force button 203: leetcode-cn.com/problems/re…

Method 1: iteration

Remove all nodes in a linked list whose values are equal to a specific value iteratively.

withtempRepresents the current node. iftempThe next node of is not empty and the node value of the next node is equal to the givenval, you need to delete the next node. Deleting the next node can be done by:iftempThe node value of the next node is not equal to the givenval, the next node is reserved, willtempMove to the next node.

When the next node of temp is empty, the list traversal ends, and all nodes with a value equal to val are deleted.

In terms of implementation, since the head node of the linked list may need to be deleted, dummy node dummyHead is created, dummyHead. Next =head, temp=dummyHead is initialized, and then the linked list is traversed for deletion. DummyHead. Next is the head node after the delete operation.

The code is as follows:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while(temp.next ! =null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else{ temp = temp.next; }}returndummyHead.next; }}Copy the code

Complexity analysis

  • Time complexity: O(n), where n is the length of the list. You need to traverse the list once.
  • Space complexity: O(1).

Method two: recursion

The definition of linked list is recursive, so linked list problems can often be solved recursively. This problem requires the deletion of all nodes in the linked list whose value is equal to a specific value. It can be implemented recursively.

For a given linked list, all nodes except head are deleted, and then the value of head is determined to be equal to the given val. If the value of head is equal to val, then head needs to be deleted, so the head node after deletion is head.next. If the node value of head is not equal to val, head is retained, so the head node after the delete operation is head. The above process is a recursive process.

Recursion terminates if head is empty, and head is returned directly. When head is not empty, delete recursively, then determine whether the node value of head is equal to val and decide whether to delete head.

The code is as follows:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        returnhead.val == val ? head.next : head; }}Copy the code

Complexity analysis

  • Time complexity: O(n), where n is the length of the list. You need to go through the list once in the recursion.

  • Spatial complexity: O(n), where n is the length of the linked list. The spatial complexity depends primarily on the recursive call stack, which does not exceed n layers at most.