LeetCode - 19. Remove Nth Node From End of List // Java

문제

 

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

Follow up: Could you do this in one pass?

 

Example 1:

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

---

풀이

 

끝에서 N번째에 위치한 노드를 삭제하는 문제이다.

 

Follow up의 조건을 위해 탐색 시간을 최소로 사용하는 알고리즘을 생각해야 했다.

 

따라서, 탐색을 통해 각 Node를 List에 저장한 뒤 끝에서 N번째 Node를 삭제하는 방식으로 구현했다.

 

주의할 점은, N번째 Node가 Head이거나, Tail일 경우 예외처리를 해주어야 한다는 것이다.

 

---

코드

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> li = new ArrayList();
        
        ListNode temp = head;
        
        while(temp != null){
            li.add(temp);
            temp = temp.next;
        }
        
        int index = li.size() - n;
        
        if(index == 0){
            return head.next;
        }
        else if(index == li.size() - 1){
            li.get(index - 1).next = null;
        }
        else{
            li.get(index - 1).next = li.get(index + 1);
        }
        
        return head;
    }
}