To the chase

Delete the penultimate node of the linked list

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 = 2Copy the code

Example 2:

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

Example 3:

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

Resolution:

To delete the penultimate NTH node, the idea is simple:

The next pointer on the last node of the node points to the next node of the node. The deletion of a linked list is actually a pointer change. The node may still exist, but is no longer pointed to by next on any node in this list.

So there are several steps.

Step 1: Find the NTH to last node.

You can refer to the previous article: three algorithms to find the penultimate KTH node in the linked list

Here we use a two-pointer traversal.

Step 2: Find the pre before deleteNode

DeleteNode = deletenode.next deleteNode = deletenode.next deleteNode = deletenode.next

Step 3: Connect the next node

Step 4: Boundary issues

  • Return an empty list if only one element exists
  • If you delete the first element of the list, there is no pre node, and there is no pre-.next. You can go straight back to head.next
/**
 * 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) {
    if (head.next === null) return new ListNode().next
    let p = head
    let deleteNode = head
    let index = 0
    let pre = null
    while(p) {
        if (index >= n) {
            pre = deleteNode
            deleteNode = deleteNode.next
        }
        index++
        p = p.next
    }
    pre === null ? head = head.next : pre.next = deleteNode.next
    return head
};
Copy the code