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

mrcode 發布于2019-08-14 12:37 / 1023人閱讀

摘要：先用快指針向前走步，這樣快指針就領先慢指針步了，然后快慢指針一起走，當快指針到盡頭時，慢指針就是倒數第個。注意因為有可能刪除頭節點，我們需要一個代碼快指針先走步從開始慢指針和快指針一起走刪除當前的下一個節點

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負載均衡

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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