19. Remove Nth Node From End of List

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

 

연결리스트의 끝에서부터 n번째 노드를 지우는 문제.

 

---

 

 

1. 문제 이해

 

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

간. 단. 명. 료. 연결리스트의 헤드 노드가 주어지면, 연결 리스트의 끝에서부터 n번째 노드를 지우고 연결리스트를 리턴하라.

 

제한사항

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

연결리스트 최소 사이즈는 1개, n 또한 1이상이네. 확! 인!

 

=> Follow up: Could you do this in one pass? (한번 쓱으로 ㄱㄴ?)

ㅆㄱㄴ~

 

 

---

 

2. 문제 재정의

 

 

요구사항이 워낙 명료해서...ㅋㅋㅋ 문제 그대로 헤드 노드랑 n 주어지면, 끝에서부터 n번째 노드 삭제하는 문제.

 

---

 

3. 계획 수립

 

사실 연결 리스트 두번 순회하면 그냥 끝나지만, 출제자가 한번 쓱으로 ㄱㄴ? 이라고 물었길래 그에 답해주는게 인지상정.

대장부의 14번째 자질 - 쉽지 않은 요구사항을 받더라도 승낙하고 호기롭게 해결한다.

술이 식기 전에 화웅의 목을 베고 치얼스를 건네는 관우처럼.

 

벡터를 생성, 연결리스트를 순회하며 벡터에다 노드를 담는다. 이후, 연결리스트 길이 == 벡터 길이 이고 (벡터길이 - n) 이 삭제할 노드의 인덱스이므로, 그 전 노드랑 이후 노드랑만을 연결해주면 된다.

 

 

---

 

4. 계획 검증 

 

 

시간 복잡도는 O(n), 한번의 순회로 가능. 첫번째 노드를 삭제하는 경우를 주의하면 되는데, 이럴 경우 그냥 head = head->next를 리턴하면 된다. 맨 끝 노드를 삭제하는 경우랑 중간 노드를 삭제하는 경우랑도 코드는 동일하다. 이전->next = 삭제할노드->next 이므로, 맨 끝 노드를 삭제하는 경우에는 삭제할노드->next 는 nullptr이 될꺼고 그렇지 않다면 그 다음 노드가 선택될 것이다. 연결리스트 사이즈 1일 때도 다른 추가적인 코드가 필요하지는 않다. 어차피 노드는 하나 이상은 무조건 삭제해야 하니깐.

 

---

 

5. 프로그램 구현 

 

 

/**
 * 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) {
        vector <ListNode *> nodes;
        ListNode *prev, *cur = head;
        
        while (cur != nullptr) {
            nodes.push_back(cur);
            cur = cur->next;
        };
        
        int deleteIdx = nodes.size() - n;
        
        if (deleteIdx == 0)
            return head->next;
        
        prev = nodes[deleteIdx - 1];
        prev->next = nodes[deleteIdx]->next;
        return head;
    }
};

---

 

 

6. 피드백 & 복기

 

벡터 없이 투포인터 풀이도 존재한다.

 

/**
 * 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 *slow = head,*fast = head;
        int cnt = 0;
        while(cnt < n){
            fast = fast->next;
            cnt++;
        }
        if(!fast) return head->next;
        while(fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

 

먼저 fast를 n만큼 이동시켜 놓고 이후 slow랑 fast를 같이 이동시켜서, fast가 끝에 다다르면 slow가 뒤에서 n만큼 떨어진 공간에 존재하므로, 이 slow->next를 slow->next->next와 연결시킨다. 좋은 접근이구만!