leetcode19 Remove Nth Node From End of List 從鏈表中移除

YPHP 發布于2019-08-14 18:05 / 452人閱讀

摘要：雖然時間復雜度還是但是顯然我們可以再一次遍歷中完成這個任務。現在跳出下標的思路，從另一個角度分析。快慢節點之間的距離始終是。當快節點到達終點時，此時的慢節點就是所要刪去的節點。

題目要求

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

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

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