[Java] LeetCode 19번 Remove Nth Node From End of List

싱글 링크트 리스트에서 뒤에서 n번째의 노드를 삭제하여 return 하는 문제이다.

자바에서 제공하는 List 자료구조를 사용하는 것이 아니라, 주어진 싱글 링크드 리스트인 ListNode를 사용해서 푸는 것이 핵심이라고 생각된다. 

싱글 링크드 리스트이기 때문에 앞에서 몇번째인지는 알 수 있지만, 뒤에서 몇번째인지는 알기가 어렵다. 그래서 먼저 리스트의 사이즈를 구하고, 뒤에서 몇번째가아니라 앞에서 몇번째를 지우는 문제로 바꿔준다. 

리스트의 사이즈가 1인 경우는 null을 리턴해줘야되고, 첫번째 노드를 지우는 경우에도 head.next를 return 해줘야된다. 

이외에는 중간노드.next = 중간노드.next.next 로 값을 변경해주면 된다.

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int nodesLen = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            nodesLen++;
        }
        if (nodesLen == 1) {
            return null;
        } else if (n == nodesLen) {
            return head.next;
        } else {
            cur = head;
            for (int i = 0; i < nodesLen - 1 - n; i++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
            return head;
        }
    }
}