/**
*
* 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
* <p>
* 进阶:你能尝试使用一趟扫描实现吗?
*
*/
//思路分析
//1. 计算来链表的长度,用链表的长度-倒数第n个节点,就是顺序删除的节点
//2. 单向链表删除节点需要找到这个节点的前一个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
//数据jiaoyan
if (head == null) {
return null;
}
//定义辅助指针指向链表的第一个节点,因为头指针不能动
ListNode cur = head;
//定义变量保存链表的长度
int count = 0;
//当循环结束时,链表的长度即为count
while (true) {
if (cur == null) {
break;
}
count++;
cur = cur.next;
}
// 链表长度为 count,要删除倒数第n个,即顺数的count - n个
int order = count - n;
//判断是否要删除第一个节点
if (order == 0){
head = head.next;
}
//再遍历链表找到要删除节点的前一个节点
cur = head;
for (int i = 1; i < order - 1; i++) {
cur = cur.next;
}
//循环结束时 cur指向要删除节点的前一个节点
//判断是不是要删除最后一个节点
if (n != 1) {
cur.next = cur.next.next;
}else {
cur.next = null;
}
//返回头节点
return head;
}
原文:https://www.cnblogs.com/mx-info/p/14758288.html