This is the fourth day of my participation in the More text Challenge. For details, see more text Challenge

Delete the NTH node from the reciprocal of the linked list (Question 19)

The title

Give you a linked list, remove the NTH node from the reciprocal of the list, and return the head node of the list.

Advanced: Can you try using a scan implementation?

Example 1:

Input: head = [1,2,3,4,5], n = 2Copy the code

Example 2:

Input: head = [1], n = 1Copy the code

Example 3:

Input: head = [1,2], n = 1Copy the code

Tip:

  • The number of nodes in the list issz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

link

Leetcode-cn.com/problems/re…

explain

I have to say that this idea is still quite a lot, the method of iteration twice is not mentioned, is the most common solution, the focus is on this advanced:

Can you try using a scan?

So one scan is just one iteration, which is a little bit of a headache, how do you know when the last element is the NTH element when you iterate once?

After thinking about it, the author got the answer that it was to record the result of each iteration and put it into an array. After the iteration was completed, the n-1st element was taken from the back, and then the node replacement was finished.

Can never think of, there is a double pointer solution, is indeed the idea of clear ah.

Your own answer (two iterations)

It’s easy to iterate twice, first take the total length of the list, then subtract n from the total length, then iterate to this position and replace the next value.

var removeNthFromEnd = function(head, n) {
  var count = -1
      dummyHead = new ListNode(0, head)
      node = dummyHead
  while (node) {
    node = node.next
    count++
  }
  node = dummyHead
  while (count - n) {
    node = node.next
    count--
  }
  node.next = node.next.next
  return dummyHead.next
};
Copy the code

The implementation is pretty simple, so there’s nothing to say about it, but the thing to notice is probably the count variable, because we’re starting with a node, so count is initialized to -1.

Your own answer (stack)

The stack method is much simpler than the two iterations. As explained in the explanation section, you take all the nodes, put them in an array, and then count them from the back.

var removeNthFromEnd = function(head, n) {
  var count = -1
      dummyHead = new ListNode(0, head)
      node = dummyHead
      stack = []
  while (node) {
    stack.push(node)
    node = node.next
    count++
  }
  stack[count - n].next = stack[count - n + 1].next  
  return dummyHead.next
};
Copy the code

Similarly, to avoid having only one element of the link removed, a head node is added and count is initialized to -1

Better method (double pointer)

Double Pointers are also easy to understand, so let’s say I have two Pointers and I start at the starting point.

And then the fast pointer starts out, and where does it start out? We start at a point n nodes away from the slow pointer, and then the slow pointer starts again, and the two Pointers go together.

When the fast pointer is null, the position of the slow pointer is the position we want, and then modify next.

However, it is also impossible to avoid the case that only one link element is removed, so a judgment should be added in the final processing. If there is only one linked list and only one element, the next of the list should be returned directly; otherwise, the node of the slow pointer should be changed.

var removeNthFromEnd = function(head, n) { var dummyHead = new ListNode(0, head) first = dummyHead second = dummyHead count = -1 prenode = null while (second) { while (count ! == n) { second = second.next count++ } if (second) { first = first.next second = second.next prenode = first } } if (! prenode) { head = head.next } else { prenode.next = prenode.next.next } return head };Copy the code

The above code is the author looked at the double pointer after their own writing, and the difference between the original answer is traversal of the internal, the original answer of the internal assignment conditions look a little around, the author here simply put the node value iteration together, feel a little clearer.

👇 :

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { let dummyHead = new ListNode('-',head); // Let p = dummyHead; // Slow pointer let q = dummyHead; // Fast pointer let count = 0; // Count let preDelNode = null; While (q){// fast pointer goes first q = q.next; If (q && count >= n){p= p.ext; preDelNode = p; } count++; } // Delete the target node if(! preDelNode ) head = head.next; Else {predelNode. next = predelNode.next; } return head; };Copy the code

In fact, the feeling is ok, see what kind of method to use it.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ