记录leecode刷题思路
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 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]
思路一：
首先一般的想法为先得到链表的长度length，然后通过长度找到需要跳过的点的前一个（length-n-1），进行跳转
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode listNode = head;
int length =0;
while (listNode!=null){
length++;
listNode=listNode.next;
}
if(length-n==0){
return head.next;
}
listNode =head;
for(int i=0;i<length;i++){
if(i==length-n-1){
listNode.next = listNode.next.next;
break;
}
listNode =listNode.next;
}
return head;
}
}
思路二：双指针
首先将fast指针先移动n个位置
然后同时移动fast、slow指针，这样能够保证两者之间的间距为n
当fast指针移动到链表结尾处时，slow指针的下一个正好是需要删除的节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow =head;
while (n--!=0){
fast=fast.next;
}
if(fast==null){
return head.next;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return head;
}
}
