[문제풀이] Leetcode 19. 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.

입출력 예시:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

✨ 풀이

/**
 * Definition for singly-linked list.
 * public 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) {
        
        ListNode start = new ListNode(0);
        // 더미 노드 하나 생성
        ListNode front = start, back = start;
        // front와 back이라는 포인터 모두 0에 세팅
        start.next = head;
        // 더미 노드 뒤에 head 붙여주기
        // (head가 [1,2,3,4,5]라면 [0,1,2,3,4,5]가 된다)
        
        for(int i = 1; i <= n+1; i++){
            back = back.next;
        } // back이라는 포인트를 n번째 노드로 옮긴다
        
        while(back != null) {
            front = front.next;
            back = back.next;
        }
        // back이 null 될 때까지 n만큼의 간격을 유지하며
        // front와 back 포인터를 한칸씩 움직여준다
        
        // back이 null 됐을 때 = 리스트노드의 끝에 도달했을 때
        front.next = front.next.next;
        // front 포인터는 제외해야 하는 노드를 한 칸 건너뛴다.
        
        return start.next;
        // 더미 노드를 제외한 리스트노드를 반환한다.
    }
}

풀이 노트:

• 리스트노드 문제풀이에 (거의) 필수인 더미 노드를 우선 생성한다.
• 리스트노드이기 때문에 배열처럼 길이를 구해서 풀 수 없다.
• 때문에 마지막에 도달하여 null이 되는 포인터와, 제외해야 할 수 전까지 움직일 포인터 2개가 필요하다.
• ListNode 개념을 100프로 이해 못했는데 이 문제를 통해서 감을 잡은 것 같다.