This is the 21st day of my participation in the Gwen Challenge in November.
The title
Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.
Example 1:
Input: head = [1,2,3,4,5], n = 2 output: [1,2,3,5] example 2
Input: head = [1], n = 1 Output: [] Example 3:
Input: head = [1,2], n = 1
Tip:
The number of nodes in the linked list is sz 1 <= sz <= 30 0 <= node. val <= 100 1 <= n <= sz
Double traversal is definitely a good way to solve the problem, but they’re asking us to do it once, so we have to think a little bit differently.
We can assume that if double Pointers p and q are set, when Q points to the last NULL and the number of elements separated between p and q is N, then the requirement of deleting the next pointer to P is fulfilled.
Set the double Pointers P and Q, both pointing to the virtual node dummyHead, and move Q until the number of elements separated between p and Q is N. Move P and Q at the same time. Until q points to NULL and the next node of P points to the next node
code
We can assume that if double Pointers p and q are set, when Q points to the last NULL and the number of elements separated between p and q is N, then the requirement of deleting the next pointer to P is fulfilled. * 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 root = cur1 = cur2 = new ListNode(-1, head); Let length = 0; While (cur1.next) {cur1 = cur1.next; length ++; } let start = length -n; While (start--) {cur2 = cur2.next} cur2.next = cur2.next-next; Return root.next; // return the header};Copy the code