构建一个网站,简答题网站建设步骤,flash网站设计实例,可以做网站的网络【Leetcode】19. 删除链表的第N个节点 1. 题目介绍2. 方法一#xff1a;计算链表长度逻辑流程:代码复杂度分析 1. 题目介绍
题目描述 给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。 示例 1#xff1a; 输入#xff1a;head [1,2,… 【Leetcode】19. 删除链表的第N个节点 1. 题目介绍2. 方法一计算链表长度逻辑流程:代码复杂度分析 1. 题目介绍
题目描述 给你一个链表删除链表的倒数第 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] 提示 链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz 2. 方法一计算链表长度
逻辑流程:
输入是一个链表
1 - 2 - 3 - 4 - None创建一个虚拟头结点 dummy它的 next 指向链表的实际头结点 head。 这一步是为了处理边缘情况比如当要删除的是头节点时可以避免额外的条件判断。
dummy - 1 - 2 - 3 - 4 - None其中 dummy 是一个虚拟头结点它的 next 指向实际的头结点 1。
调用辅助函数 getLength 来计算整个链表的长度。初始化一个指针 cur指向 dummy。 这个指针将用来遍历链表直到找到待删除节点的前一个节点。 如果执行了 ListNode cur dummy;那么 cur 也指向 dummy 所指向的那个节点。 此时cur 和 dummy 的关系如下
dummy (cur) - 1 - 2 - 3 - 4 - None使用一个循环使 cur 向后移动 length - n 1 次这样 cur 就会停在待删除节点的前一个位置。 如果执行 cur cur.next;cur 将移动到下一个节点 1
dummy (cur)↓1 - 2 - 3 - 4 - None更新 cur.next 为 cur.next.next跳过当前的下一个节点即待删除节点。 如果执行 cur.next cur.next.next;这将跳过节点 2并让 1 直接指向 3
dummy (cur)↓1 - 3 - 4 - None| / |2 \ |\ |\ |4最后返回 dummy.next 作为新的头节点这是因为如果删除了原始的头节点那么新的头节点就是 dummy.next。 在这个过程中dummy 的 next 指针也被更新了因为 cur 和 dummy 指向同一个节点。所以dummy 的 next 也从 1 变成了 3。
代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy new ListNode(0, head);int length getLength(head);ListNode cur dummy;for (int i 1; i length - n 1; i) {cur cur.next;}cur.next cur.next.next;ListNode ans dummy.next;return ans;}public int getLength(ListNode head) {int length 0;while (head ! null) {length;head head.next;}return length;}
}
复杂度分析 时间复杂度O(L)其中 L 是链表的长度。 空间复杂度O(1)。
