LCR 021

题目：LCR 021

解法一：计算链表长度

遍历两次，第一次获取链表长度 L（包括虚拟节点），第二次遍历到第 L-n 个节点（从虚拟节点遍历）

    public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int L = 0;ListNode temp = dummy;while (temp != null) {L++;temp = temp.next;}temp = dummy;for (int i = 1; i < L - n; i++) {temp = temp.next;}temp.next = temp.next.next;return dummy.next;}

注意：

• 建议在头节点前添加虚拟节点，因为假如要删除的是第一个元素，就不能用前节点指向后节点的方法来删除节点，因此推荐给头节点加上前驱节点
• while 循环条件为 temp != null，而非 temp.next != null

解法二：马拉车算法

将链表所以节点压入栈中，顺序弹出，弹出n个后，栈顶元素即为删除节点的前驱节点

    public ListNode removeNthFromEnd(ListNode head, int n) {Stack<ListNode> stack = new Stack<>();ListNode dummy = new ListNode(0, head);ListNode temp = dummy;while (temp != null) {stack.push(temp);temp = temp.next;}for (int i = 0; i < n; i++) {stack.pop();}temp = stack.peek();temp.next = temp.next.next;return dummy.next;}

注意：while 循环条件为 temp != null，而非 temp.next != null

解法三：双指针

设置双指针，前指针指向第 n 个节点，后指针指向头节点，同时向后遍历，当前指针遍历到尾部时，后指针指向的即为删除节点的前驱节点

    public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);ListNode first = dummy;ListNode second = dummy;for (int i = 0; i < n; i++) {first = first.next;}while (first.next != null) {first = first.next;second = second.next;}second.next = second.next.next;return dummy.next;}

注意：while 循环条件为 temp.next != null，而非 temp != null