[LeetCode/LintCode] Remove Nth Node From End of L

Jaden 发布于2019-08-14 15:21 / 2823人阅读

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 linked list becomes 1->2->3->5->null.

Challenge

Can you do it without getting the length of the linked list?

Note

首先建立dummy结点指向head，复制链表。
然后建立快慢指针结点fast、slow，让fast比slow先走n个结点，再让fast和slow一起走，直到fast到达链表最后一个结点。由于fast比slow快n个结点，所以slow正好在链表倒数第n+1个结点。
最后让slow指向slow.next.next，就删除了原先的slow.next———倒数第n个结点。
返回dummy.next，结束。

Solution

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n <= 0) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        while (n-- != 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

GPU云服务器云服务器 nth-of-type Nth remove remove()方法

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

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

[LeetCode/LintCode] Design Twitter/Mini Twitter

摘要：首先建立按时间戳从大到小排列的，找到中的，出其中在中存在的，把每一个的推特链表放入，再从中取头十条推特的放入结果数组。 Design Twitter Note 建立两个HashMap，一个存user，一个存tweets。以及整型的时间戳timestamp。user的k-v pair是userId-follower_set，tweets的k-v pair是userId-tweets_li...

honmaple 2019-08-14 15:31 评论0 收藏0
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 19：删除链表的倒数第N个节点 Remove Nth Node From End

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

周国辉 2019-07-31 11:30 评论0 收藏0
[Leetcode] Remove Nth Node From End of List 移除倒数第N

摘要：先用快指针向前走步，这样快指针就领先慢指针步了，然后快慢指针一起走，当快指针到尽头时，慢指针就是倒数第个。注意因为有可能删除头节点，我们需要一个代码快指针先走步从开始慢指针和快指针一起走删除当前的下一个节点 Remove Nth Node From End of List 最新更新的解法和思路：https://yanjia.me/zh/2018/11/... Given a link...

mrcode 2019-08-14 12:37 评论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