删除链表的倒数第 N 个结点（java算法）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
一共有两种解法
第一种是我自己写的
/** * 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 chang = head; int L = 0; //求得了链表的长度 while(chang != null){ chang = chang.next; L++; } if(n < L){ //找到倒数第n个的前（qian）结点的位置 ListNode qian = head; ListNode node = head; for(int i = 2;i <= L-n;i++){ qian = qian.next; } qian.next = qian.next.next; } //考虑到删除头节点的情况 if(n == L){ head = head.next; } return head; } }
第二种是LeetCode上给的标准答案
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); int length = getLength(head); ListNode cur = dummy; for (int i = 1; i < length - n + 1; ++i) { cur = cur.next; } cur.next = cur.next.next; ListNode ans = dummy.next; return ans; } public int getLength(ListNode head) { int length = 0; while (head != null) { ++length; head = head.next; } return length; } }
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
