“This is the 17th day of my participation in the First Challenge 2022.

Delete the Middle Node. Delete the Middle Node

02.03. Delete intermediate nodes

The title

If a node in a linked list is neither the head node nor the tail node, it is called an “intermediate node” of the list.

Given an intermediate node of a linked list, implement an algorithm to remove that node from the list.

Implement an algorithm to delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.

For example, an incoming node C (in a-> B -> C -> D -> E -> F) is removed and the remaining list is A -> B -> D -> E -> F

Example:

Input: the node c from the linked list a->b->c->d->e->f
Output: nothing is returned, but the new linked list looks like a->b->d->e->f

Copy the code

Thinking line

Their thinking

So when we look at this problem, my first thought is, let’s iterate through the list, find the same element as the deleted list, and let the last element point to the next element that was deleted. So I can solve this problem in order n time.

But let’s look at what they gave us

/ * * *@param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {};Copy the code

They only give you one element to delete, but they don’t give you the original list. How do you do that?

If we can delete a given node without giving the original list, we need to make sure that the current node points to the next node.

So the problem changes from how to delete the intermediate node to how to make the node to be deleted become the next node.

Let’s analyze what we have in a one-way linked list. There are two properties in the list: val is the value of the list and next is the next thing the list points to.

If we change the val of the element to be deleted to the value of the next node. Next = this.Next-next. Next So that we can perfectly replace the node to be deleted with the next one. This completes the need to remove intermediate nodes.

The specific code is as follows:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {
    node.val = node.next.val;
    node.next = node.next.next;
};
Copy the code

Time complexity analysis

O(1): Our operations are constant.

This is my solution to this question. If you have any questions or better solutions, please leave a comment and interact.