0019. Remove Nth Node from End of List #

题目 #

删除给定链表的倒数第 n 个节点，并且返回头节点。
尝试使用一趟扫描实现。

思路 #

双指针 #

若要删除单链表的倒数第 n 个节点，需定位单链表的倒数第 n + 1 个节点。
考虑快慢指针，令快指针先走 n + 1步，之后双指针同步前进至快指针为空。
此时慢指针指向单链表的倒数第 n + 1 个节点。
设置哨兵节点有助于简化算法实现。

代码 #

双指针 #

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1, head), slow = sentinel, fast = sentinel;
        
        for (int i=0; i<n+1; i++) fast = fast.next;
        
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        
        return sentinel.next;
    }
}