leetcode19 Remove Nth Node From End of List 从链表中移除

YPHP 发布于2019-08-14 18:05 / 441人阅读

摘要：虽然时间复杂度还是但是显然我们可以再一次遍历中完成这个任务。现在跳出下标的思路，从另一个角度分析。快慢节点之间的距离始终是。当快节点到达终点时，此时的慢节点就是所要删去的节点。

题目要求

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.

题意就是，从链表中移除倒数第n个节点（前提是这个被移除的节点一定存在）

思路一：利用数据结构ArrayList

从题目中可知，如果我们知道这个链表的大小，就可以直接删去节点。所以按照正常思路，我们可以先从根节点遍历一遍这个链表，得出链表的size后，再删去倒数第n个，也就是正数第size-n个节点。这样意味着遍历两次这个链表。虽然时间复杂度还是O(n),但是显然我们可以再一次遍历中完成这个任务。思路一就是将ArrayList和LinkedList相结合起来，通过ArrayList的下标完成要求

public class RemoveNthNodeFromEndofList_19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        List nodeList = new ArrayList();
        ListNode start = new ListNode(0);
        start.next = head;
        nodeList.add(start);
        
        while(head != null){
            nodeList.add(head);
            head = head.next;
        }
        int index = nodeList.size() - n;
        nodeList.get(index-1).next = nodeList.get(index).next;
        
        return nodeList.get(0).next;
    }
    
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}

思路二：利用快慢指针

思路一直接利用了ArrayList的下标完成了任务。现在跳出下标的思路，从另一个角度分析。直接从题目要求入手，如果我们获得最后一个节点，那么到最后一个节点的距离为n的就是我们所要删去的节点。我们可以使用快慢节点。快慢节点之间的距离始终是n。当快节点到达终点时，此时的慢节点就是所要删去的节点。
相比于上一种方法，这种方法也只需要一次遍历，而且占用的额外存储空间更小。

public class RemoveNthNodeFromEndofList_19 {
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode start = new ListNode(0);
        start.next = head;
        ListNode slow = start;
        ListNode fast = start;
        
        for(int i = 0 ; i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 nth-of-type json中移除数据 java数组中移除 Leetcod

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

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

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
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-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
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