Leet code (Medium): 19. Remove Nth Node From End of List - JAVA

 

 

두개의 포인터를 사용하는 것이 포인트다.

초반엔 스택을 사용해서 푸는 방법을 생각했는데 그러다 보니 어차피 사라질 노드를 타겟으로 잡게되어서 고려해야할 상황들이 너무많았다.

두개의 포인터를 다음과 같은 용도로 사용한다.

 

• 첫번째 포인터: 삭제될 노드와 N만큼 차이나는 뒤쪽 노드
• 두번째 포인터: 삭제될 노드를 next로 가지는 노드

따라서 두 포인터는 N+1 만큼의 차이를 갖는다.

반복문을 통해, 첫번째 노드부터 끝까지 탐색하는데

첫번째 포인터가 마지막 노드를 넘어서 null이 될 때, 두번째 포인터는 삭제될 노드를 next로 가리키고 있고,

반복문은 멈춘다.

 

그리고 두번째 포인터의 next 를 next.next로 바꾸면 된다.

 

/**
 * 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 res = new ListNode(0, head);
        // 삭제될 노드의 전 노드
        ListNode dummy = res;

        // head를 n만큼 뒤로 밀기
        for(int i = 0; i < n; i++){
            head = head.next;
        }
        
        // head가 끝을 넘어가면 멈추게 되고,
        // 그때, dummy는 삭제될 노드의 전 노드를 가리키는 상태가됨
        while(head != null){
            head = head.next;
            dummy = dummy.next;
        }

        dummy.next = dummy.next.next;

        return res.next;
    }
}