Topic describes

18. Remove nodes from the list

Their thinking

It is a singly linked list. A singly linked list is characterized by a pointer to the next node in each node. If you want to delete a node, the previous node of the node points to the next node. Skip the node to be deleted, and the node is deleted. In JavaScript, we don’t care if this node needs to free memory at the end.

Consider three scenarios:

  • If the head node does not exist, return directly

  • If the first node is the one to be removed, return its next node directly.

  • Iterate over a single linked list with the variable cur as the head node

    • ifcurOf the next node ofvalAnd given to deletevalIf the value is equal, the node is skipped and will becur 的 nextPointer tocur.next.next:cur.next = cur.next.next;
    • Otherwise, it indicates that no node to be deleted is encountered, and the complex value of the next node is directly given to the cur node:cur = cur.nextComplete the traversal. When the node isnullIs the end of the traversal.

    Note: When the value to delete is found, the change iscurA pointer to thenext, cur.next = cur.next.nextAnd in normal traversal,curIt’s the next nodecur = cur.next

code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} val
 * @return {ListNode}* /
var deleteNode = function(head, val) {
    if(! head)return head;
    if(head.val === val) return head.next;
    let cur = head;
    while(cur.next){
        if(cur.next.val === val){
            cur.next = cur.next.next;
        }else{
            cur = cur.next
        }
    }
    return head;
};
Copy the code

conclusion

The general idea is to walk through, find the node you want to delete and then change the pointer to the preceding element to point to the next node, and then consider special cases where the head node doesn’t exist or the value of the head node is the node you want to delete.

Time complexity: THERE are n O(n) linked lists with n operations

Space complexity: O(1)