leetcode-19-删除链表倒数第n个节点

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

示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：先计算链表的长度，然后定位到要删除节点的前一个节点，该节点的next为next的next。（两次循环遍历）

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode resNode = new ListNode(-1); resNode.next = head; int length = 0; ListNode node = head; while(node != null){ length++; node = node.next; } //计算要移动的距离 length -= n; node = resNode; while(length>0){ node = node.next; length--; } node.next = node.next.next; return resNode.next; }

方法二：单次遍历

两指针遍历，先将第一个指针移动n+1次，第二个指针与第一个指针相差n，然后同时向后移动，直到第一个指针为空（而不是第一个指针的下一个指针为空）

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