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

문제

링크드리스트의 head가 주어졌을 때, 끝에서 n번째 노드를 제거하고 head를 리턴

주어진 리스트 노드의 구조는 다음과 같다

* 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) {}
* };
*/

생각할 것

• 어떤 노드를 제거할 지 찾기

1. head node만 주어졌으므로 노드들의 정보를 저장하면서 tail노드를 찾아야한다.
   a. next가 Nullptr인 노드일 것이다.
2. 뒤에서 저장된 N번째 노드정보를 찾는다.

---

• 자료구조에서 링크드리스트의 제거 원리에 따라 구현하기

1. 첫번째 노드일 경우
   a. head노드를 제거할 노드의 다음노드로 설정
2. 중간 노드일 경우
   b. 이전 노드의 next를 다음 노드로 설정
3. 마지막 노드일 경우
   c. 이전 노드의 next를 nullptr로 설정

이렇게 한다면 처음에 링크드리스트를 정보를 저장하는데만 시간복잡도가 O(n)이 소요될 것이다.

코드

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> nodes;
        ListNode* node = head;

        while(1){
            nodes.push_back(node);
            if(node -> next == nullptr) break;
            else node = node -> next;
        }

        int ridx = nodes.size() - n;
        if(ridx == 0){ // 첫번째 노드인 경우, 노드가 하나만 있는 경우 제거
            head = nodes[ridx] -> next;
        }
        else if(ridx == nodes.size() - 1){ // 마지막 노드 제거
            nodes[ridx - 1] -> next = nullptr; 
        }
        else { // 중간 노드 제거
            nodes[ridx - 1] -> next = nodes[ridx] -> next;
        }

        return head;
    }
};

개선할 점

배열을 이용해 노드들을 저장하는 것은 불필요한 공간을 낭비하게 된다.

벡터를 사용하지 않는 다른 방법으로 slow, fast포인터를 사용할 수 있다.

1. slow, fast 포인터가 head를 가리킨다.
2. fast포인터를 n만큼 먼저 이동시킨다.
3. 이후로 slow, fast 포인터를 동시에 이동시키고, fast노드가 마지막 노드에 위치할 때 멈춘다.
4. 그러면 slow포인터의 next노드가 끝에서 n번째 전의 노드를 가리키고 있을 것이다!
5. 제거할 때는 slow → next에 해당하는 노드를 slow → next → next 노드로 대체하면 된다.