LeetCode: Remove Nth Node From End of List

Remove Nth Node From End of List

Singly 링크드 리스트가 주어졌을때 뒤에서 부터 N 번째 (N 은 언제나 valid 일때) 를 remove 합니다.
예1) 1->2->3->4->5, N = 4
1->3->4->5 를 리턴하면 됩니다.
예2) 1->2->3->4->5, N = 1
1->2->3->4 를 리턴하면 됩니다. 이 문제는 한번 생각해 보시고 코드를 보시길 바랍니다.
되게 재밌있는 문제죠.

---

두개의 노드가 있다면 어떻게 될까요? 하나의 노드는 다른 노드보다 더 멀리 있는 겁니다.

두개의 노드가 N 만 큼 떨어져있다면?

---

가장 쉬운 방법은 길이를 구하는거겠죠. 하지만 그렇게 되면 O(2N) 으로 문제를 풀어야합니다. O(N) 으로도 풀 수 있죠. 힌트를 보시면 아시겠지만 일단 N 떨어진 노드를 만듭니다. 그리고 그 노드가 NULL 이 될 때 그 전에 노드는 끝에서 N 번째 떨어져 있음을 알게됩니다.

예) 1->2->3->4->5, N = 3
뒷 노드: 1 에 있음
앞 노드: 5 에 있음 (3 만큼 떨어져있음)
앞 노드가 NULL 이 된 만큼 움직이면 뒷 노드: 2에 있음. 그리고 3을 remove 하면 됨.

public ListNode removeNthFromEnd(ListNode head, int n) {
    // this takes care of edge case like n = length of list
    ListNode newHead = new ListNode(0);
    newHead.next = head;
    ListNode prev = newHead;
    ListNode next = newHead;
    // n is always valid
    for (int i = 0; i <= n; ++i) {
        next = next.next;
    }
    while (next != null) {
        prev = prev.next;
        next = next.next;
    }
    // remove node
    prev.next = prev.next.next;
    // java takes care of front node
    return newHead.next;
}