This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic Description:

237. Remove a node from a linked list – LeetCode (leetcode-cn.com)

Write a function that removes a given (non-trailing) node from a linked list. The only argument passed to the function is the node to be deleted.

There is a linked list — head = [4,5,1,9], which can be expressed as:

The sample a

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

Example 2

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

Tip:

  • A linked list contains at least two nodes.
  • All nodes in a linked list have unique values.
  • The given node is a non-trailing node and must be a valid node in the list.
  • Do not return any results from your function.

Thought analysis

This is a little tricky, the list doesn’t give you the head, so it’s a little different.

There’s one thing in the solution that’s pretty clear, so I copied it

If we want to delete a node from a linked list, we do this:

For example, in the linked list [4, 5, 1, 9], when we want to delete node 5, we change the pointer to node 4 above node 5 to point to the node next to node 5, which is node 1:

But this problem only tells us which node to delete, and we don’t know what was the last node of that node, so what do we do?

Since we need to know the last node to delete a node, if we can’t know the last node, we find a node that knows the last node, make it the node to delete, and then delete it.

That sounds like a mouthful, right? Ok, look at an example directly!

Still the [4, 5, 1, 9] list, still delete node 5.

First, we make node 5 a “no need to delete” node by assigning it the value of the next node:

In this way, the second node 1 and the third node 1, no matter which one we delete, can get the final result [4, 1, 9]. Since the second node is not easy to delete, we will delete the third node

Change the pointer to the second node 1 to point to the fourth node 9, so that the third node 1 is removed:

AC code

class Solution {
    fun deleteNode(node: ListNode?).{ node? . `val` = node? .next? . `val` node? .next = node? .next? .next } }Copy the code

conclusion

This problem is not difficult, but a little pit, Leetcode’s title readability is really not good.

reference

Delete node from list – Delete Node from list – force link (LeetCode) (leetcode-cn.com)

Diagram to delete a linked list node | Python/Golang – delete node in the list – force buckle (LeetCode) (leetcode-cn.com)