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 zero
sz
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:
fast
The fast hand goes aheadn+1
步slow
Pointer to current distancefast
From the firstn
Zero 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 node
preHead
To set uppreHead.next = head
, this can solve the above problem, delete the penultimaten
After 0 nodes, returnpreHead.next
Can be - The other way is,
fast
The fast hand goes aheadn
After step, judgefast.next
Whether it isnull
, i.e.,fast
Is the last node, and if so, yeshead
For the bottom firstn
At this point, the problem can be simplified as deleting the head node; If not,fast = fast.next
,fast
One step further,slow
For the bottom firstn+1
To solve the above problems.
Solution 1: AddpreHead
node
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 separatelyn
node
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