[LeetCode, 리트코드] Remove Nth Node From End of List

1. Problem

 

주어진 링크드 리스트에서 끝에서 n번째 노드를 삭제하고 그 head를 반환해라. n은 언제나 유효한 수다.

 

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.

 

2.Solution

 

2번 순회를 해서 구하는 방법도 있지만 메모리를 써서 순회하는 동안 각 지점의 ListNode의 위치를 저장하는 vector 자료구조를 만들어서 풀면 한 번만 순회해서 풀 수 있다.

 

 

3. Code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> locToNum;
        
        ListNode* mock = new ListNode(-1);
        mock->next = head;
        ListNode* curr = head;
        int total = 0;
        
        while(curr){
            locToNum.push_back(curr);
            total++;
            curr = curr->next;
        }
        
        if(total == n){
            ListNode* prev = mock;
            prev->next = head->next;
        }
        else{
            ListNode* prev = locToNum[total - n - 1];
            prev->next = locToNum[total-n]->next;
        }
        
        return mock->next;
    }
};