19. 删除链表的倒数第N个节点
一、题目描述
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例 :
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
二、解题思路
一、递归遍历
1、解题思路
设置全局变量total,index,Nth,,分别代表节点总数,递归坐标,倒数第 n 个节点数。
设置虚拟头节点,并指向head;因为当要删除的节点为第一个节点时,需要一个前驱进行操作。
进行递归遍历,每进入递归函数且改节点存在时total加一。当递归至空节点时,将help复制为节点总数,
寻找到倒第N个节点前驱,即可解答该题啦!满足total==Nth+index即代表该节点为前取,即可进行删除操作。
2、代码
public class Solution{ //采用递归遍历 至第倒N+1个节点进行删除 int total = 0;//节点总数 int index=0;//递归坐标 int Nth = 0;//被删除的n public ListNode removeNthFromEnd(ListNode head, int n) { if(head== null||n==0)return head; //虚拟头节点(当被删除的为第一个时,需用到前驱节点) ListNode dummyNode = new ListNode(-1); dummyNode.next= head; Nth = n; removeNthHelper(dummyNode); return dummyNode.next; } private void removeNthHelper(ListNode head) { if(head== null){ index=total+1; return; } total++;//计算节点总数 ListNode cur = head.next; removeNthHelper(cur); index--;//递归节点坐标 if((index+Nth)==total){//定位至被删节点的前一位 head.next= cur.next; } } }
二、窗口法
1、解题思路
- 设置虚拟头节点,并指向head;因为当要删除的节点为第一个节点时,需要一个前驱进行操作。
- 设置双指针p,q,首先将q指针往后移至n+1个节点,使指针p执行p,q组成的窗口的倒第N个节点的前驱。
- 移动该窗口,直至指针q移至末尾,则指针p指向的即为该链表的倒第N个节点的前驱。即可进行删除操作。
2、代码
public class Solution { //双指针法至窗口 public ListNode removeNthFromEnd(ListNode head, int n) { if(head== null||n==0)return head; //虚拟头节点(当被删除的为第一个时,需用到前驱节点) ListNode dummyNode = new ListNode(-1); dummyNode.next= head; //双指针 先将两指针距离相隔n+1个,指针q为倒第n个节点的前驱 ListNode p = dummyNode,q=dummyNode; for(int i =0;i<=n;i++)q = q.next; //窗口移动,直至移至末尾 while (q!=null){ p=p.next; q=q.next; } //此时q指针便是倒第n个节点的前驱 p.next = p.next.next; return dummyNode.next; } }