LeetCode 19:删除链表的倒数第N个节点 Remove Nth Node From End of List-阿里云开发者社区

开发者社区> 爱写Bug> 正文

LeetCode 19:删除链表的倒数第N个节点 Remove Nth Node From End of List

简介: 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 Given a linked list, remove the n-th node from the end of list and return its head. 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n 保证是有效的。
+关注继续查看

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

Given a linked list, remove the n-th node from the end of list and return its head.

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

Note:

Given n will always be valid.

进阶:

你能尝试使用一趟扫描实现吗?

Follow up:

Could you do this in one pass?

解题思路:

这道题很有意思,虽然很简单,但是很考验一个人的思维。最先想到的方法就是遍历整个链表得到长度,减去 n 得到实际应该删除的节点的位置了。然而由于单链表删除操作的特殊性,得到位置之后仍然需要再遍历一次来删除该节点。

进阶要求是一次遍历完成该题,想想是否有好的方法?

假设链表长度为 L ,定义一个指针先走 n 步,此时该指针还剩下 L-n 个节点即可完成该链表的遍历。而第 L-n 个节点不就是题目要求的的要删除的倒数第 n 个节点吗?这时候只需要再定义一个指针,让它与之前的指针同时遍历,当第一个指针遇到空节点时(null 节点),该指针即指向删除的节点。

值得注意的的是,指向应当删除的节点并无法删除它,应当指向该删除节点的前一个节点。

Java:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode curA = head;
        ListNode curB = head;
        for (int i = 0; i < n; i++) curA = curA.next;
        if (curA == null) {//如果走了n步之后该节点指向空节点,则该链表只有一个节点
            head = head.next;
            return head;
        }
        while (curA.next != null) {//当第一个指针的下一个节点为空时,该指针指向最后一个节点,而指针curB 走了L-n-1步,即指向该删除节点的前一个节点
            curA = curA.next;
            curB = curB.next;
        }
        curB.next = curB.next.next;//将本来指向应当删除节点地址指向应当删除节点的下一个节点的地址
        return head;
    }
}

Python3:

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        curA,curB=head,head
        for i in range(n):
            curA=curA.next
        if not curA:
            head=head.next
            return head
        while(curA.next):
            curA=curA.next
            curB=curB.next
        curB.next=curB.next.next

欢迎关注公.众号一起刷题:爱写Bug

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
从零开始学 Web 之 DOM(四)节点
大家好,这里是「 Daotin的梦呓 」从零开始学 Web 系列教程。此文首发于「 Daotin的梦呓 」公众号,欢迎大家订阅关注。在这里我会从 Web 前端零基础开始,一步步学习 Web 相关的知识点,期间也会分享一些好玩的项目。
1020 0
Treeview的Node拖动Node节点移动
Treeview的Node拖动Node节点位置移动并重新排序存储。 关键代码: private void treeView1_DragDrop(object sender, DragEventArgs e)//拖动 ...
688 0
java:利用xpath删除xml中的空节点
原始xml内容: 1 2 3 b1 4 5 123 6 7 8 9 10 11 可用下面的代码去掉 、这二个空节点 (注 中间有一个空格,不算空节点) 1 @Test...
1039 0
《jQuery Cookbook中文版》——1.11 删除DOM元素
在使用remove()从DOM中删除选择的元素时,它们并没有从jQuery包装器集中删除。这意味着,从理论上说,可以继续操作它们,甚至可以在必要的时候将它们重新添加到DOM中。
1245 0
fastdfs的动态扩容及删除节点
fastdfs的动态扩容及删除节点
77 0
删除文件的恢复
最近帮别人恢复U盘的一些文件信息,看了一下sleuthkit工具的使用,当然最简单还是在windows下使用easy recover,当时fat的文件系统还是存在许多缺点,它文件占用的cluster记录在fat表中,以链式的结果,如果删除的文件不连续,可以讲恢复的文件可能是坏的.
563 0
C# 通过传入节点name及节点value,来删除XML相应节点
//通过传入节点name及节点value,来删除相应节点 public static string OperateXml(string keyInfo, string valueInfo) { if (File.Exists(filePath)) { XmlDocument xmlDoc = new XmlDocument(); xmlDoc
1147 0
+关注
爱写Bug
欢迎关注公众号:爱写Bug
85
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载