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

 

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

LeetCode - The World's Leading Online Programming Learning Platform

문제 :

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

 

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

 

Example 2: 

Input: head = [1], n = 1
Output: []

 

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

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

---

Summary

마지막으로 부터 N번째 노드를 삭제하기 위해서는 단순히 생각해보면 마지막 노드를 찾은 이후에 거기서 부터 뒤로 N번 가면 된다. 하지만 단방향 linked list이기 때문에 뒤로는 갈 수 없다. 

쉽게 생각해보면 tail까지 length가 저장되어 있으면 그걸로 부터 N 전으로 이동해서 삭제를 하면 되겠지만 여기서는 length가 없으니 length를 구하면 된다. 

따로 counter를 저장하여 pointer를 이동하고 nullptr가 나올 때 까지 counter를 증가시킨다. 

counter에서 N만큼을 빼면 그 위치가 삭제해야되는 노드이고 N-1만큼 이동한 pointer를 가지고 pointer->next = pointer->next->next로 연결하면 N번째 노드가 삭제된다.

 

아마 이렇게 풀어도 전혀 문제가 없겠으나 좀 더 스마트하게 풀어보자!

 

Solution

/**
 * 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* newHead = new ListNode(0);
        newHead->next = head;
        ListNode* slow = newHead;
        ListNode* fast = newHead;
        for (int i = 0; i < n; i++) {
            if (fast == nullptr) return nullptr;
            fast = fast->next;
        }
        while (fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return newHead->next;
    }
};

 

토끼와 거북이 알고리즘을 알고 있는가? 모른다면 아래 글을 참고하자.

https://dev.to/alisabaj/floyd-s-tortoise-and-hare-algorithm-finding-a-cycle-in-a-linked-list-39af

Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List

 

slow가 거북이 이고 fast가 토끼라고 하면 slow는 1칸씩, fast는 2칸씩 이동하게 되면 토끼가 노드의 마지막에 도착했을 경우 거북이의 위치는 전체 노드의 중앙에 위치하게된다. 또한 Linked list가 순환한다면, 토끼와 거북이는 어느순간 만나게 된다. (Cycle detection algorithm)

https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare

Cycle detection - Wikipedia

 

이 컨셉을 활용하여 이 문제를 풀어보자. 

마지막에 도착하기 N번의 위치를 알기 위해서는 토끼를 먼저 N번 이동시킨다. 

N번 이동시킨 토끼와 0번째 위치에서 거북이를 동시에 출발 시키면 토끼가 마지막 노드에 도착하게 되면!

마지막 노드 - N의 위치에 거북이가 도착하게 된다.

정말 신기하지 않은가?! 

그런데 우리가 알아야되는건 N-1의 위치이다. 이를 알아야 N+1과 연결하여 N을 지워낼 수 있다. 

조금 꼼수를 써서 head앞에 newHead를 만들어 추가해 준다. 이렇게 되면 자연스럽게 거북이가 N-1이 위치에서 멈추게 된다. 그림을 그려가며 생각해보면 쉽게 이해할 수 있을 것 이다. 이는 이 글을 보는 독자에게 맡긴다.

 

위의 solution 코드는 합격은 되지만 메모리 릭이 있다 :) 

한번 수정해서 풀어보는 것도 실력 향상에 도움이 될 것 같다!