Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Delete the last NTH node from the linked list

Delete the penultimate node of the linked list, medium

I. Title Description:

We did 19 in the last question. We deleted the NTH node from the penultimate of the linked list. After that, did XDM notice that we actually scanned the linked list twice

And they say, can we do this with one scan?

Can it be done? Must be able to achieve ah, we brush a problem is not brush over, but also need to analyze how to solve it will be better, faster, more robust

Just like in the work, we do a thing, not finished calculate, also need to review, sum up efficient experience

1. What ideas does this question examine? What’s your thinking?

So we’ve already done this problem, so how do we do that just by going through the list once?

And from our experience last time, we know how to find the NTH to the last node and delete it, right

We calculated the length of the entire list, and then we figured out how many times we had to offset it from scratch

So this time, can we offset the pointer from scratch, and we know where we’re going to stop? You don’t need to calculate the length of the list

So we can simulate:

If there is a fixed distance between a red pointer and a black pointer, when the black pointer takes a step earlier, the red pointer will also take a step forward until the black pointer reaches the end of the list

So at this time, the distance between the red pointer and the black pointer will not change, strictly maintain the distance, do not overtake, will not lose

So let’s go back and think about it, is this red pointer equivalent to the NTH node from the bottom?

If we want to delete the penultimate NTH node, then we can also use this way, through the list can find the penultimate NTH node?

Similarly, since we want to delete the last NTH node, we need to find the first node of the last NTH node, so that we can easily delete the nodes that need to be deleted when we operate the linked list

So, let’s just go ahead and add a help node to the top of the list, and make it start by saying that we need to find the first node to delete the node, something like this

The purple nodes above are the nodes we need to delete. The operation of this piece is the same as that of the previous article, so I won’t repeat it here

So the next step is to translate the code according to the idea, which is actually to use the double pointer method to deal with this problem, there are a lot of scenarios about the double pointer processing problem

Three, coding

According to the above logic and analysis, we can translate into the following code, pay attention to the processing of fast and slow Pointers

The encoding is as follows:

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // Define a help node and place it on the first node of the list. We can default to 0 and define it as any other number
    helper := &ListNode{0, head}
    // Define a fast pointer and a slow pointer
    quick, slow := head, helper
    // The fast pointer runs n times
    for i := 0; i < n; i++ {
        quick = quick.Next
    }
    // The quick pointer runs once, and the slow pointer always has to be offset n+1 more times to catch up with the quick pointer
    for; quick ! =nil; quick = quick.Next {
        slow = slow.Next
    }
    // Find the next node where the node to delete is a slow pointer
    slow.Next = slow.Next.Next
    return helper.Next
}
Copy the code

Read the above code, or more clear bar, the logic of the code and the logic of deduction is consistent, simple enough, enough to understand

It only needs to deal with the logic of fast and slow Pointers, which can be achieved by scanning one side of the linked list, and then completing the deletion of the NTH node from the penultimate of the linked list, nice

Iv. Summary:

The time is O(n), which is the length of the list, and because we walked through it, the space is O(1), we only introduced constant space consumption

Delete the NTH node from the list

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~