19. Remove Nth Node From End of List[Medium]

19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Example

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

题解

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp, result, record;
        // 待偏移节点
        temp = head;
        // 初始节点
        record = result = new ListNode(0, head);
        /**
         * 偏移量问题，要尾部第N个节点，可以先从头部偏移N个节点，然后在拿原始节点和其一起偏移，结束时原始节点应该还剩下N个节点
         * N = 1
         * 1->2->3->4   ->    2->3->4
         *
         * 1->2->3->4
         * 2->3->4
         *
         * 一起偏移后原始节点还剩个4，这也正是需要删除的节点，但此时并不知道他前一个节点是什么，所以用一个初始节点来做头节点
         *
         * 4
         */
        for (int i = 0; i < n; i++) {
            temp = temp.next;
        }

        while (temp != null) {
            temp = temp.next;
            record = record.next;
        }

        // 移除待删除元素
        record.next = record.next.next;

        // 初始节点是自定义的，要从初始节点下一位开始
        return result.next;