Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

18. Remove nodes from the list

Given a head pointer to a one-way linked list and the value of a node to delete, define a function to delete that node.

Returns the head node of the deleted list.

Note: this question has been changed from the original question

Example 1:

Input: head = [4,5,1,9], val = 5 Output: [4,1,9]Copy the code

Example 2:

Input: head = [4,5,1,9], val = 1 Output: [4,5,9]Copy the code

 

Description:

  • They make sure that the values of the nodes in the list are different
  • If you’re using C or C++, you don’tfree 或 deleteThe node is deleted

Train of thought

  1. Because they said that the value of each node in the list must be different, so that means we only need to delete one element, which is a big step faster than others;
  2. First of all, we should consider whether the node to be deleted is the head node, because the deletion of the head node is different from other nodes. Normally, when we delete a node in the linked list, we get the previous nodeprevChange,prev.nextThe head node is not availableprev, you can also insert another node directly in front of the list. Here, I choose direct judgment.
  3. If it is not the head node, then each time we traverse a node, we determine whether its next node is the value we want to delete. If so, we exit the loop.

implementation

/** * 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) {
    // Determine if it is a head node
    if (head.val === val) {
        return head.next;
    }

    let cur = head;

    // If the node is not the head node, delete it directly each time
    Cur. next = cur.next = cur.next = cur.next = cur.next = cur.next = cur.next = cur.next = cur.next = cur.next
    while (cur && cur.next) {
        if (cur.next.val === val) {
           cur.next = cur.next.next; 
           break;
        }

        cur = cur.next;
    }

    return head;
};
Copy the code

The results of

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.