![删除链表的倒数第N个节点(java实现) 删除链表的倒数第N个节点(java实现)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
题目:
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
看到这个题,我们得有一些思路:
1.删除的那个节点需要找到,那就需要双指针pre和index,
2.双指针开始都是指向头节点,index先走到比头节点的大n的地方,
3.然后两个指针同时往后遍历,当index的下一个为空时,此时pre指向的就是需要删除的那一个节点,
4.删除的这个节点还需要分情况:(1)、它的后续节点不为空,(2)、它的后续为空,
5.若后续不为空就需要后面的去覆盖它,若为空,就只需要设置为null就可以了。
代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(null == head){
return null;
}
if(n <= 0){
return head;
}
ListNode pre = head;
ListNode index = head;
ListNode orghead = head;
for(int i = 1;i < n ;i++){ //让i先走n步
index = index.next;
if(null == index){
return null;
}
}
while(null != index.next){ //到n的地方,pre也开始遍历
orghead = pre;
pre = pre.next;
index = index.next;
}
//删除时得考虑删除节点是否有后续节点
if(null != pre.next){
pre.val = pre.next.val; //有就往前移
pre.next = pre.next.next;
}else{
if(null == pre.next){ //没有后续,只需把它设置为空就可以
return null;
}
orghead.next = null;
}
return head;
}
}
我测试了一下,不判断它的后续节点是否为空,直接赋值,出现了空指针异常。
不考虑后续节点的代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = head;
ListNode index = head;
for(int i = 1;i < n;i++){
index = index.next;
if(index == null){
return null;
}
}
while(index != null){
index = index.next;
pre = pre.next;
}
pre.next = pre.next.next;
return head;
}
}
出现的异常: