leetcode-19 remove nth node from end of list

題意: 給定一linked list, 移除倒數第n 個元素,只能遍歷一次

解題思路: 只能掃一次,這個條件還蠻煩的,訣竅就是用一個array把每個指標都存起來,至於linked list可以新增一個頭插在最前面,這樣處理起來會方便許多,這樣複雜度為O(N),空間複雜度為O(N), N為linked list 長度

p.s. leetcode上的解答為使用兩個指標,彼此相距n,同時移動,當其中一指標到達底時,另一指標即為要移除的指標,這個做法時間複雜度為O(N) (雖然和我的作法時間複雜度一樣,但實際上會較慢,因為多掃了n個元素),空間複雜度為O(1)

程式碼如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count=0;
        ListNode* arr[10000];
        ListNode* ori=new ListNode(0);
        arr[0]=ori;
        ori->next=head;
        
        while(head!=NULL)
        {
            count++;
            arr[count]=head;
            head=head->next;
        }
        
        if(count-n+2<=count)
            arr[count-n]->next=arr[count-n+2];
        else
            arr[count-n]->next=NULL;
        return  ori->next;
        
    }
};