题目描述

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：

给定的 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 removeNthFromEnd(ListNode head, int n) { ListNode dum = new ListNode(-1); dum.next = head; ListNode fast = dum; ListNode slow = dum; while(n > 0){ fast = fast.next; n--; } while(fast.next != null){ fast =fast.next; slow = slow.next; } slow.next = slow.next.next; return dum.next; } }

递归

用递归找到整个链表的结尾

class Solution { int deleteIndex=-1; public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dum=new ListNode(); dum.next=head; delete(dum,n,0); return dum.next; } public void delete(ListNode node,int n,int index){ if(node.next!=null){ index++; //用递归找到整个链表的结尾 此时已经找到结尾了 delete(node.next,n,index); index--; //进行删除 if(deleteIndex==index+1){ node.next=node.next.next; } }else{ //给删除的节点位置的变量赋值 deleteIndex=index-n+1; } } }