LeetCode/19. Remove Nth Node From End of List

head가 주어졌으므로 어렵게 생각할 필요 없이 vector에 순서대로 다 담은 다음 idx로 편하게 작업했다.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> nodes;
        ListNode* cur = head;
        
        while(cur != nullptr)
        {
            nodes.push_back(cur);
            cur = cur->next;
        }
        //지울 타겟
        int target = nodes.size() - n;
        //첫번째 노드를 삭제하는 것이라면
        if(n == nodes.size())
        {
            if(nodes.size()==1)
                head = nullptr;
            else
                head = nodes[1];
        }
        //마지막 노드를 삭제하는 것이라면
        else if(n == 1)
        {
            nodes[target-1]->next = nullptr;
        }
        else
        {
            nodes[target-1]->next = nodes[target+1];
        }
        
        
        return head;
    }
};

혹은 two pointer를 이용한 풀이도 있다.

우선 slow와 fast 포인터를 n만큼 벌려두고 fast가 마지막 노드에 닿았으면 slow->next가 제거 대상에 해당하는 노드이다.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head, *slow = head;
        
        //slow와 fast의 간격을 n만큼 벌린다
        for(int i=0; i<n; ++i)
        {
            fast = fast->next;
        }
        
        //제거할 대상이 첫번째 노드라면
        if(fast==nullptr)
            return head->next;
        
        //그게 아니라면
        while(fast->next)
        {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};