LeetCode：19. 删除链表的倒数第 N 个结点（中等）

问题链接

19. 删除链表的倒数第 N 个结点

问题描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例

解题思路

0.理解

在不考虑释放被删除节点对应的空间的情况下，我们只需要将倒数第n个节点的前节点指向倒数第n个节点的后节点即可。

1.借助数组

这可能算取巧，遍历一遍链表，将链表中的每一个节点存入list，这时候你想怎么操作就怎么操作了......

2.双指针

新建一个表头，将两个指针放在表头往后遍历：
一个指针先跑，使得两个指针之间隔着n-1个节点；
当跑得快的指针跑到了最后一个节点时，另外一个指针跑到了倒数n+1个节点；
此时，让倒数n+1个节点的next指向next.next即可。

代码示例（JAVA）

1.借助数组

/**
 * Definition for singly-linked list.
 * 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) {
        List<ListNode> nodeList = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            nodeList.add(node);
            node = node.next;
        }

        if (nodeList.size() == n) {
            return head.next;
        }
        nodeList.get(nodeList.size() - n - 1).next = n != 1 ? nodeList.get(nodeList.size() - n + 1) : null;
        return head;
    }
}

执行结果

2.双指针

/**
 * Definition for singly-linked list.
 * 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 newHead = new ListNode(0, head);
        ListNode first = head;
        ListNode second = newHead;

        for (int i = 0; i < n - 1; i++) {
            first = first.next;
        }
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }

        second.next = second.next.next;
        return newHead.next;
    }
}

执行结果