Linked List | Remove Nth Node From End of List

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

끝에서 N번째 노드를 지우라는 문제이다. 맨먼저 생각할 수 있는 가장 간단한 방법은, 끝까지 한번 여행을 한 후, 총 갯수를 알아내어 n번만큼 빼고 다시 가게 해서 그 노드를 지우는 방법이다. 하지만 이 방법은 최대 2N의 Travel을 해야한다. 이것 말고, 두개의 포인터를 사용해서 차이를 두고 loop을 도는 방식으로 접근하게되면 더 빠르게 찾아낼 수 있다. 처음에는, n만큼을 덜 가서, 그 전 노드에서 그 다다음 노드로 연결하는것이 복잡해 보였지만, dummy node를 맨 앞에 만들어두고, 어떠한 경우든지 (맨 첫번째나 맨 마지막 노드를 지워야하는 경우, 변수가 생기기 때문에), 똑같은 방식으로 지워낼 수 있게 구현했다.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

* Time Complexity: O(N)

* Space Complexity: O(1)

 

O(N)으로 해결 가능하다. 결국, fast 포인터가 맨 마지막 노드에 도달할때까지 돌기 때문에, 어떤 경우든 Linked List의 길이만큼 프로그램이 동작한다. 스페이스같은 부분에서는, fast, slow 그리고 dummy node를 생성했으나, O(1)이다. 이 해법으로 최고 속도를 달성했고, 아마 새로운 dummy node의 크기때문인지 메모리는 상위 58.88%에 그쳤지만 나쁘지 않다. (미세한 경쟁일것이라고 추측한다).

자, 관동지방 포켓몬중 뒤에서 100번째 포켓몬 나와랏!

 

Reference

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

Remove Nth Node From End of List - LeetCode