This is the 19th day of my participation in the August Wenwen Challenge.More challenges in August

The title

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:

Enter: head = [1,2,3,4,5], n = 2

Output:,2,3,5 [1]

Example 2:

Enter: head = [1], n = 1

Output: []

Example 3:

Enter: head = [1,2], n = 1

Output: [1]

 

Tip:

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

Their thinking

Idea 1

The classic two-pointer application, if you want to remove the NTH node from the bottom, move FAST n steps, and then move fast and slow together until FAST points to the end of the list. Just delete the nodes that slow points to.

Here’s the idea, but pay attention to a few details.

It is divided into the following steps:

  • First, I recommend using virtual headers to handle the logic of removing real headers
  • Define fast and slow Pointers with initial values as virtual headers, as shown in the figure below:

  • Fast takes n+1 step first. Why n+1? Because only in this way can slow point to the last node where the node was deleted (easy to delete).

  • Fast and slow move at the same time, so fast points to the end, as in the problem:

  • Delete the next node pointed to by Slow as shown in the figure below:

code

/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
    let ret = new ListNode(0, head),
        slow = fast = ret;
    while(n--) fast = fast.next;
    if(! fast)return ret.next;
    while (fast.next) {
        fast = fast.next; 
        slow = slow.next
    };
    slow.next = slow.next.next;
    return ret.next;
};
Copy the code

Idea 2: The speed pointer

To delete the last NTH node in the list, all we need to know is the last NTH +1 node, and then delete the next node of the last NTH +1 node

Steps:

Use two Pointers:

  • fastThe fast hand goes aheadn+1 步
  • slowPointer to current distancefastFrom the firstnZero nodes, starting withhead

Then, fast and slow synchronize forward until fast. Next is null

At this point, fast is the last node and slow is the n+1 node from the bottom to the bottom. At this point, the problem changes to deleting the successor node of SLOW in the linked list

However, there is a problem. When the length of the linked list is N, FAST can advance less than N +1 nodes, so there are two solutions at this time:

  • Create a head nodepreHeadTo set uppreHead.next = head, this can solve the above problem, delete the penultimatenAfter 0 nodes, returnpreHead.nextCan be
  • The other way is,fastThe fast hand goes aheadnAfter step, judgefast.nextWhether it isnull, i.e.,fastIs the last node, and if so, yesheadFor the bottom firstnAt this point, the problem can be simplified as deleting the head node; If not,fast = fast.next ，fastOne step further,slowFor the bottom firstn+1To solve the above problems.

Solution 1: AddpreHeadnode

var removeNthFromEnd = function(head, n) {
    let preHead = new ListNode(0)
    preHead.next = head
    let fast = preHead, slow = preHead
    // Quick n+1 step first
    while(n--) {
        fast = fast.next
    }
    // Go fast and slow together
    while(fast && fast.next) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return preHead.next
};
Copy the code

Solution two: Deal with the penultimate separatelynnode

var removeNthFromEnd = function(head, n) {
    let fast = head, slow = head
    // Take n steps quickly
    while(--n) {
        fast = fast.next
    }
    if(! fast.next)return head.next
    fast = fast.next
    // Go fast and slow together
    while(fast && fast.next) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return head
};
Copy the code

Time complexity: O(n)

Space complexity: O(1)

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way

“Front-end brush” No.19