“This is the seventh day of my participation in the First Challenge 2022.

Day arch algorithm, work does not donate tang.

Linked list data structures are rarely used. The advantage of linked lists is that the insertion time complexity is good O(1).

Idle talk less Syria, blunt over the thing!

For a linked list, delete the NTH node from the penultimate of the list and return the first node of the list.

Such as:

Input: head = [1,2,3,4,5], n = 2 Output: [] Input: head = [1,2,3,5], n = 1 Output: [1]Copy the code
  • The number of nodes in the linked list is sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Answer key:

If we define the length of the list to be L, then the reciprocal NTH term, the positive l-n+1 term, the preceding term is the L-n term;

  • Double pointer method

Let the backward pointer forward and backward pointer advance backward at the same time after the difference between them is N, then when forward reaches the destination, that is, when forward. Next is null, backward just reaches the previous term of the penultimate NTH term and connects the front and back terms of the penultimate NTH term;

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode(0, head)
    let forward = dummy, backward = dummy
    while (n--) {
        forward = forward.next
    }
    while (forward.next) {
        forward = forward.next
        backward = backward.next
    }
    backward.next = backward.next.next
    return dummy.next
};
Copy the code

The submission is approved.

In addition to double Pointers, there is also a simple violent conversion of the list to an array:

  • Array method

Convert the linked list to a pure array, store the value of the list in the array, delete the penultimate NTH number, and then convert the array to a linked list;

var removeNthFromEnd = function(head, n) { let newArr = [] let dummy = new ListNode() let newList = dummy while(head){ newArr.push(head.val) head = head.next } newArr.splice(newArr.length - n, 1) for(let i = 0; i < newArr.length ; i++){ newList.next = new ListNode(newArr[i]); newList = newList.next; } return dummy.next };Copy the code

Extension: The linked list nodes can be successively deposited into the array stack, and then the last n elements of the stack are popped up to expose the first node of the NTH to the last node of the NTH to the last node of the list:

var removeNthFromEnd = function(head, n) { const dummy = new ListNode(0, head) const stack = new Array() let pushList = dummy while (pushList ! = null) { stack.push(pushList) pushList = pushList.next } for (let i = 0; i < n; i++) { stack.pop() } let peek = stack[stack.length - 1] peek.next = peek.next.next return dummy.next };Copy the code

The key of a linked list is to determine the point of the next node. Linked lists and arrays can also be converted to each other, but it will be a bit stiff. Bi-directional Pointers are more flexible.

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~