hot 100 19. 删除链表的倒数第 N 个结点

问题描述

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

样例输入

head=[1,2,3,4,5],n=2

样例输出

[1,2,3,5]

评测用例规模与约定

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

解析

采用灵神的思路，增加一个哨兵节点以防倒数第n个节点就是第一个节点。
两个指针相当于也是一个先走n+1步，然后两个一起走，第一个走到最后一个时第二个走到了倒数n+1个节点然后指向下一个的下一个就行了。
为何这样数学证明下：
假设链表长度为l
首先一个先走n+1步
然后走到末尾需要走l-n-1步
第二个走了l-n-1步倒着数就是倒数n+1.

参考程序

classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNoded=newListNode(0,head);ListNodel=d;ListNoder=d;while(n-->0)r=r.next;while(r.next!=null){l=l.next;r=r.next;}l.next=l.next.next;returnd.next;}}

难度等级

⭐️⭐️⭐️⭐️（1~10星）

以个人刷题整理为目的，如若侵权，请联系删除~