[LeetCode C++] 19. Remove Nth Node From End of List

⭐️ 난이도

 

Medium

---

⭐️ 문제

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Remove Nth Node From End of List - LeetCode

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Linked list의 head가 주어졌을 때, 끝에서 n번째의 노드를 삭제하고, 리스트의 head를 반환하시오.

 

---

⭐️ Follow-up

 

Could you do this in one pass?

 

---

⭐️ Idea flow

 

이 문제에서 양방향 리스트가 아니라 단방향 리스트로 주어진다.

따라서 앞 쪽으로 진행이 가능하지만, 뒤에서 다시 되돌아가는 것은 안된다.

 

또한 follow-up의 요구에 따라 one-pass로 문제를 해결해야 한다.

따라서 map을 이용하여 linked-list를 끝까지 쭉 돌면서 key에는 인덱스를, value에는 ListNode*를 넣는다.

동시에 cnt를 1씩 증가시키면서 노드의 개수를 센다.

 

이후 (cnt - n) - 1의 next 포인터를 (cnt - n) + 1을 가리키게 하면, 뒤에서 n번째 노드로 이어지는 링크를 끊을 수 있다.

 

만일 끝에서 n번째인 노드가 첫 번째 노드라면, 위의 과정 없이 바로 두 번째 노드를 반환하면 된다.

 

 

---

⭐️ Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* result = head;
        unordered_map<int, ListNode*> hashmap;
        int idx = 0, cnt = 0;
        
        while(result){
            hashmap[idx] = result;
            cnt++;
            idx++;
            result = result->next;
        }
        
        int delete_node = cnt - n;
        if(delete_node == 0){
            head = hashmap[delete_node + 1];
        }
        else{
            hashmap[delete_node - 1]->next = hashmap[delete_node + 1];
        }
        return head;
    }
};

 

 

---

⭐️ Feedback

 

Space complexity: O(1)

 

내가 위에서 사용했던 방법은 O(n)의 extra space를 필요로 한다.

하지만 다른 사람의 코드를 보니 공간 복잡도를 O(1)로 할 수 있는 방법이 있었다.

 

바로 two pointers를 사용하는 방법이다.

1. 먼저 두 개의 포인터 fast, slow를 선언한다. 이 두 포인터 모두 head로 초기화 시켜준다.

2. fast를 n만큼 다음 노드로 이동시켜 준다. 이로써 slow와 fast의 간격이 n칸이 된다.

3. 이후 fast->next가 null이 될 때까지 fast와 slow 모두 다음 노드로 이동시켜 준다.

   fast가 null이 된다는 말은 곧 fast 포인터가 linked-list의 제일 끝에 도달했다는 뜻이다.

   그리고 fast와 slow의 간격이 n칸이므로, slow->next가 끝에서 n번째 노드이다.

4. slow->next = slow->next->next를 함으로서 링크를 다다음 노드로 옮겨준다.

   이로써 끝에서 n번째 노드를 제거했다.

 

 

[전체 코드 보기]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head, *slow = head;
        for(int i = 0; i < n; i++){
            fast = fast->next;
        }
        if(!fast)   return head->next;
        
        while(fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};