当前位置: 首页 > 后端技术 > Java

牛客网高频算法系列-BM9-删除链表最后n个节点

时间:2023-04-02 09:46:13 Java

牛客网高频算法系列-BM9-删除链表最后n个节点题目描述给定一个链表,删除链表链表的倒数第n个节点,返回链表头指针。见原标题:BM9删除链表的倒数第n个节点解决方法一:双指针法首先考虑两种特殊情况:如果原链表为空,则直接返回null。如果k不是正数,直接返回null。否则,使用双指针求解,求解过程如下:因为可以删除头节点,所以先设置一个虚拟头节点dummyNode,并指向原头节点;然后,遍历链表,将快结点指向第n-1个结点;如果遍历后fast为null或者fast的next为空,说明链表长度小于n,没有最后n个节点,直接返回null;否则,fast和slow指针一起移动,直到fast移动到倒数第二个节点,此时slow为倒数第二个n+1节点;然后去掉slow的下一个节点,也就是倒数第二个n节点;最后返回dummyNode.next删除第n个节点后n个节点后的新链表。代码publicclassBm009{/***双指针方法**@paramheadListNodeclass*@paramnintinteger*@returnListNodeclass*/publicstaticListNoderemoveNthFromEnd(ListNodehead,intn){//如果原链接list如果为空,直接返回nullif(head==null){returnnull;}//如果n不是正数,直接返回nullif(n<=0){returnnull;}//因为可以删除头结点,所以先设置一个假头结点,指向原来的头结点ListNodedummyNode=newListNode(-1);dummyNode.next=head;ListNodefast=dummyNode;//将fast节点指向第n个节点-1节点for(inti=0;i