思路:
首先找到倒数第N个结点
- 第一种方式 先统计链表的节点数，然后再次遍历len-N即可得到倒数第N个结点，然后将前一个节点的next指针指向next的下一个节点
- 使用快慢指针，快指针先跑N个结点然后慢指针开始跑，等快指针到达尾节点后，慢指针的位置就是倒数第N个结点位置
代码如下:
/*** 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 removeNthFromEnd01(ListNode head, int n) {if (head == null) {return head;}List<ListNode> list = new ArrayList<>();while (head!=null){list.add(head);head=head.next;}list.remove(list.size()-n);if (list.isEmpty()){return null;}ListNode node=list.get(0);ListNode cur=node;for (int i = 1; i < list.size(); i++) {cur.next=list.get(i);cur=cur.next;}cur.next=null;return node;}//计数方式 删除倒数第n个 先算出 链表长度public static ListNode removeNthFromEnd02(ListNode head, int n) {if (head==null){return null;}int len=0;ListNode node=head;while (node!=null){len++;node=node.next;}if (n>len){return head;}if (n==len){return head.next;}//倒数第N个 就是整数len-n个ListNode cur=head;int index=0;while (cur!=null){//走到前一个节点时if (index==len-n-1){cur.next=cur.next.next;break;}cur=cur.next;index++;}return head;}//使用快慢指针 快指针先走n个节点 慢指针再开始走 当快指针到达null节点时候 慢指针正好到达倒数第n个节点//并且添加哑节点 来简化边界条件 防止如果删除的头节点问题public static ListNode removeNthFromEnd(ListNode head, int n) {if (head==null){return null;}ListNode dummy = new ListNode(0, head);ListNode fast=dummy ;ListNode slow=dummy;for (int i = 0; i <= n; i++) {fast=fast.next;}while (fast!=null){slow=slow.next;fast=fast.next;}slow.next=slow.next.next;return dummy.next;}
}
