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

周国辉发布于2019-07-31 11:30 / 3012人阅读

摘要：给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后，链表变为说明给定的保证是有效的。值得注意的的是，指向应当删除的节点并无法删除它，应当指向该删除节点的前一个节点。

给定一个链表，删除链表的倒数第 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

GPU云服务器云服务器倒数第二条记录 linux链表的安全访问合并链表的c语言学生链表的c语言代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/45232.html

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

摘要：给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后，链表变为说明给定的保证是有效的。值得注意的的是，指向应当删除的节点并无法删除它，应当指向该删除节点的前一个节点。给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 Given a linked list, remove the n-th node from the ...

qiangdada 2019-08-16 18:40 评论0 收藏0
leetcode-019-删除链表倒数第N个结点(Remove Nth Node From End

摘要：第题给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。因为，若有一个真正的头结点，则所有的元素处理方式都一样。但以第一个有效元素为头结点，就导致算法的不一致，需要单独处理第一个有效元素头结点。 leetcode第19题 Given a linked list, remove the n-th node from the end of list and return its h...

brianway 2019-08-23 14:34 评论0 收藏0
leetcode19 Remove Nth Node From End of List 从链表中移除

摘要：虽然时间复杂度还是但是显然我们可以再一次遍历中完成这个任务。现在跳出下标的思路，从另一个角度分析。快慢节点之间的距离始终是。当快节点到达终点时，此时的慢节点就是所要删去的节点。题目要求 Given a linked list, remove the nth node from the end of list and return its head. For example, ...

YPHP 2019-08-14 18:05 评论0 收藏0
leetcode 19 Remove Nth Node From End of List

摘要：题目详情题目要求输入一个和一个数字。要求我们返回删掉了倒数第个节点的链表。想法求倒数第个节点，我们将这个问题转化一下。我们声明两个指针和，让和指向的节点距离差保持为。解法使点和点的差距为同时移动和使得到达的末尾删除倒数第个节点题目详情 Given a linked list, remove the nth node from the end of list and return it...

chaosx110 2019-08-15 14:41 评论0 收藏0
leetcode 19. Remove Nth Node From End of List

摘要：这题也是携程年暑假实习生的笔试题。最开始想的解法就是，先循环求链表的长度，再用长度，再循环一次就能移除该结点。结果对的，但是超时了。再返回整个链表。 Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2...

bigdevil_s 2019-08-20 15:16 评论0 收藏0