<strike id="24yos"></strike>

<ul id="24yos"></ul>

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

YPHP 發(fā)布于2019-08-14 18:05 / 435人閱讀

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

題目要求

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.

題意就是，從鏈表中移除倒數(shù)第n個節(jié)點（前提是這個被移除的節(jié)點一定存在）

思路一：利用數(shù)據(jù)結(jié)構(gòu)ArrayList

從題目中可知，如果我們知道這個鏈表的大小，就可以直接刪去節(jié)點。所以按照正常思路，我們可以先從根節(jié)點遍歷一遍這個鏈表，得出鏈表的size后，再刪去倒數(shù)第n個，也就是正數(shù)第size-n個節(jié)點。這樣意味著遍歷兩次這個鏈表。雖然時間復(fù)雜度還是O(n),但是顯然我們可以再一次遍歷中完成這個任務(wù)。思路一就是將ArrayList和LinkedList相結(jié)合起來，通過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的下標完成了任務(wù)。現(xiàn)在跳出下標的思路，從另一個角度分析。直接從題目要求入手，如果我們獲得最后一個節(jié)點，那么到最后一個節(jié)點的距離為n的就是我們所要刪去的節(jié)點。我們可以使用快慢節(jié)點。快慢節(jié)點之間的距離始終是n。當快節(jié)點到達終點時，此時的慢節(jié)點就是所要刪去的節(jié)點。
相比于上一種方法，這種方法也只需要一次遍歷，而且占用的額外存儲空間更小。

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

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~