1. Title Description

Given a linked list, delete the NTH node from the bottom of the list and return the head 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 = 1 output: []Copy the code

Example 3:

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

Tip:

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

Second, train of thought analysis

Linked lists cannot be traversed in reverse order, so the difficulty of this problem is how to locate the “penultimate NTH”. We can convert “the NTH from last” to: “the positive len-n + 1”. We can go through it first to get len, and then we can go through it again to get len-n + 1.

But is there a way not to go through it twice? Use the fast or slow pointer:

  • The fast pointer takes n steps first,
  • The fast and slow hands go forward together
  • When the fast pointer reaches the last node, both Pointers stop
  • The position that the slow pointer points to is the previous node to the NTH node from the bottom

At this point, it is convenient for us to delete:

slow.next = slow.next.next
Copy the code

AC code

/** * @param {ListNode} head * @param {number} n * @return {ListNode} */ const removeNthFromEnd = function(head, N) {// initialize dummy dummy const dummy = new ListNode() // dummy to head dummy. Next = head Dummy let fast = dummy let slow = dummy // ==0){fast = fast. Next n--} while(fast. Next){fast = fast. Next slow = slow // return dummy. Next};Copy the code

Four,

  • The use of fast and slow Pointers can be better in space for time
  • “The NTH to last” can be converted to: “the positive len-n + 1”.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign