字节面试算法题
删除链表的倒数第N个节点
思路：首先设置两个节点 first ,second 都指向head节点，然后先让first向后移动，直到second和first的间隔恰好为N的时候，first和second一起向后移动，直到first.next == null 的时候，那么second所指的结点就是要删除的结点。
代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; ++i) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
ListNode ans = dummy.next;
return ans;
}
}复杂度分析
- 时间复杂度：O(L)，其中 L 是链表的长度。
- 空间复杂度：O(1)。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-09-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读