大家好,我是程序员吴师兄,欢迎来到图解 LeetCode 专栏,在这个专栏我将使用图片和动画帮助你更好的思考。
AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!
今天分享的题目来源于 LeetCode 上第 19 号问题:删除链表的倒数第 N 个节点。
一、题目描述
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
二、题目解析
直接来思考如何通过 一次遍历 来解决问题。
由于只允许一次遍历,所以不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该移除了。
那么就需要用两个指针来帮助解题,pre 和 cur 指针。
首先通过一个循环,让 cur 指针 先 向前走 N 步,如果此时 cur 指向空,说明 N 为链表的长度,则需要移除的为首元素,那么此时返回 head->next
即可。
如果 cur 存在,再继续往下走,此时 pre 指针也跟着走,直到 cur 为最后一个元素时停止,此时 pre 指向要移除元素的前一个元素,再修改指针跳过需要移除的元素即可。
三、动画描述
隐藏内容
四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//构建虚拟节点
ListNode dummy = new ListNode(0);
// 虚拟节点指向原链表的头部
dummy.next = head;
// 构建两个指针,都指向虚拟节点 dummy
ListNode pre = dummy, cur = dummy;
// 通过一个循环,让 cur 指针 先 向前走 n 步
for (; n > 0 && pre.next != null; --n) cur = cur.next;
// 删除的是链表头部节点
if (n != 0) return head.next;
// cur 存在,两个指针一直向前移动
while (cur.next != null) {
pre = pre.next;
cur = cur.next;
}
// 通过修改指针的位置,删除了需要修改的节点
pre.next = pre.next.next;
return dummy.next;
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(k)。
空间复杂度
空间复杂度为 O(1)。
七、相关标签
- 链表
- 双指针