Leetcode question of the Day – “Remove the NTH node from the list”

【 Title 】

Delete the NTH node from the penultimate list

【 topic description 】

Given a list, delete the NTH node from the penultimate of the list and return the first node of the list. Advanced: Can you try using a scan implementation?

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 Output: [1]

Sz 1 <= sz <= 30 0 <= node. val <= 100 1 <= n <= sz

【 答 案 】

[Double pointer method]

The difficulty in this problem is to find the NTH node from the end of the list. We know that the position of the next node in the linked list can only be known by traversing the previous node. The next node of the last node in the linked list is empty. Because it’s the NTH node to the last, it’s definitely not feasible to go through the forward derivation, and we only know when we’re at the end. In view of this, we can use the fast and slow Pointers, the fast pointer first goes forward n positions, and then the slow pointer starts from the first position. When the fast pointer reaches the last node, the slow pointer just reaches the NTH node from the bottom.

Meanwhile, since we need to delete the penultimate NTH node, we need to know the penultimate NTH +1 position, so that we can link the penultimate n+1 with the penultimate n-1.

[Code implementation]

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode fast = head; ListNode slow = head; ListNode slowPre = head; int i = 0; while (fast ! = null) { if (i >= n) { slow = slow.next; } if (i >= n+1) { slowPre = slowPre.next; } fast = fast.next; i++; } if (slow==head) {ListNode newHead = slow. Next; slow.next = null; return newHead; } else { slowPre.next = slowPre.next.next; return head; }}Copy the code