[Leetcode] Remove Nth Node From End of List 移除倒数第N

mrcode 发布于2019-08-14 12:37 / 914人阅读

摘要：先用快指针向前走步，这样快指针就领先慢指针步了，然后快慢指针一起走，当快指针到尽头时，慢指针就是倒数第个。注意因为有可能删除头节点，我们需要一个代码快指针先走步从开始慢指针和快指针一起走删除当前的下一个节点

Remove Nth Node From End of List 最新更新的解法和思路：https://yanjia.me/zh/2018/11/...

Given a linked list, remove the nth node from the end of list and
return its head.For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list
becomes 1->2->3->5. Note: Given n will always be valid. Try to do this
in one pass.

迭代法 复杂度

时间 O(N) 空间 O(1)

思路

典型的快慢指针。先用快指针向前走n步，这样快指针就领先慢指针n步了，然后快慢指针一起走，当快指针到尽头时，慢指针就是倒数第n个。不过如果要删除这个节点，我们要知道的是该节点的前面一个节点。另外，如果要删的是头节点，也比较难处理。这里使用一个dummy头节点，放在本来的head之前，这样我们的慢指针从dummy开始遍历，当快指针为空是，慢指针正好是倒数第n个的前一个节点。最后返回的时候，返回dummy的下一个。

注意

因为有可能删除头节点，我们需要一个dummyhead

代码

java

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 快指针先走n步
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        // 从dummy开始慢指针和快指针一起走
        ListNode curr = dummy;
        while(fast != null){
            fast = fast.next;
            curr = curr.next;
        }
        // 删除当前的下一个节点
        curr.next = curr.next.next;
        return dummy.next;
    }
}

python

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        fast = dummy
        for i in range(0, n):
            fast = fast.next
        slow = dummy
        while(fast.next is not None):
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

GPU云服务器云服务器 nth-of-type 倒数第二条记录 Nth nth负载均衡

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

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

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-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
移除链表倒数第n个元素

摘要：移除链表倒数第个元素给定一个链表，移除倒数第个元素，返回链表头部。移除链表倒数第n个元素 Remove Nth Node From End of List 给定一个链表，移除倒数第n个元素，返回链表头部。 Given a linked list, remove the nth node from the end of list and return its head. Note:...

yhaolpz 2019-07-25 12:04 评论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/LintCode] Remove Nth Node From End of L

Problem Given a linked list, remove the nth node from the end of list and return its head. Example Given linked list: 1->2->3->4->5->null, and n = 2. After removing the second node from the end, the l...

Jaden 2019-08-14 15:21 评论0 收藏0