(Linked List, Medium) Remove Nth Node From End of List

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

뒤에서부터 N번째 노드를 지워야 한다.
그래서 제일 처음 푼 방식은 각 노드 순회마다, 그 노드로부터 next가 없는 마지막 노드까지의 길이를 구하도록 했다.

그 다음 prev가 있으면 포인터를 갈아치워 주고,
prev가 없으면 head를 current.next로 갈아치워 준다.
왜? prev 갱신된 적이 없으면 시작점부터 틀려먹었기 때문에.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode current = head;
        ListNode prev = null;

        while (current != null) {

            ListNode next = current;
            int gap = 0;
            
            while (next != null) {
                next = next.next;
                gap++;
            }

            if (gap == n) {
                if (prev != null) {
                    prev.next = current.next;
                } else {
                    head = current.next;
                }
                break;
            }

            prev = current;
            current = current.next;
        }

        return head;
    }
}

시간복잡도는 당연히 O(N^2)이다.
신기한 점은 submissions에서는 beats 100%로 나오긴 한다. (leetcode에서 테스트케이스 엄청 작게 주나봄)

---

더 좋은 방법을 Solution에서 찾아봤다.
O(N)으로 해결 가능한디, 원리가 재밌다.

투포인터를 이용한 방법인데 미리 fast를 n칸만큼 밀어놓고
fast의 next가 없을때까지 (마지막 노드가 될때까지) 두 포인터를 함께 증가시킨다.

그렇게 함으로써 결국 slow와 fast 사이에는 지워질 노드가 남게 된다.

즉 ...
fast를 n칸 먼저 이동시키면, fast와 slow 사이에 n칸 거리 차이가 생기고
이후 둘을 동시에 한 칸씩 움직이면, fast가 리스트의 끝에 도달할 때 slow는 끝에서 n번째 노드의 이전 노드에 도달

참고로 fast 먼저 n칸 밀었을 때 fast가 null이 된다면
head가 지워져야 할 노드라는 뜻이므로 head.next를 리턴하면 되나보다.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;

        for (int i=0; i<n; i++) {
            fast = fast.next;
        }

        if (fast == null) {
            System.out.println("aaa");
            return head.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}