力扣: 删除链表的倒数第N个元素

需求

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

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

进阶：你能尝试使用一趟扫描实现吗？

分析

如果是删除链表的第 N 个元素, 那就很 easy , 所以第一个简单的方法就是 将倒数第N个转变为 第N 个, 这就要得到链表的长度了.

//  求出链表的长度
int size = 0;
ListNode cur = preHead.next;
while( cur != null ){size++;cur = cur.next;
}

然后 倒数第N个元素, 其实就是 第 ( size - n ) 个元素:

public ListNode removeNthFromEnd(ListNode head, int n) {//  虚拟头结点ListNode preHead = new ListNode(-1, head);//  求出链表的长度int size = 0;ListNode cur = preHead.next;while( cur != null ){size++;cur = cur.next;}//  遍历 然后 删除 第 (size - n) 个元素cur = preHead;for( int i = 0; i < (size - n); i++ ){cur = cur.next;}cur.next = cur.next.next;return preHead.next;
}

执行:

进阶

进阶：你能尝试使用一趟扫描实现吗？

我能 !

可以用双指针法, 先让 快指针往后走 n 步, 然后再开始遍历, 快慢指针一块走, 当快指针.next指向空的时候, 这个慢指针指向的下一个就是要删除的元素.

public ListNode removeNthFromEnd(ListNode head, int n) {//  虚拟头结点ListNode preHead = new ListNode(-1, head);ListNode fast = preHead;ListNode slow = preHead;for( int i = 0; i < n; i++ ){fast = fast.next;}while( fast.next != null ){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return preHead.next;
}

运行:

结尾

以上 是我对这道算法的一些遐想和延伸, 可能不是最优解, 但是算法的优化嘛 本身就是一个思索的过程, 能在这个思索和迭代的过程中有所收获和乐趣就是在成长了, 欢迎大家一起来交流更多的解答…