[LeetCode] 19. Remove Nth Node From End of List, Medium

1. 문제

• 연결 리스트와 정수 n이 주어질 때, n 번째 노드를 제외한 리스트를 반환하라.

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let slow = head, faster = head;

    for(let i =0; i< n; i++) faster = faster.next;

    if(!faster) return head.next;

    while(faster.next) {
        slow = slow.next;
        faster = faster.next;
    }

    slow.next = slow.next.next;


    return head;
};

• 처음에는 리스트에 포인터 하나를 두고, 해당 포인터+1에서 n번 째 노드가 null인 애를 찾아서 어떻게 해보려고 했는데, 특정 케이스에서 실패해서 다른 사람 풀이를 참고해봤다.
• 핵심은 두 포인터가 있고, 하나는 하나 씩 탐색하는 포인터로 사용하고 하나는 n 번째 앞에 있는 노드를 가리키는 포인터로 사용하는 것.
• 그래서 처음에 빠른 포인터를 먼저 위치시키고, 노드가 2개만 존재하는 리스트에서 null 인 경우는 첫 번째 노드가 삭제 대상이므로 head의 next를 반환.
• 그 외는 빠른 포인터가 마지막 노드를 가리킬 때 까지 이동한 뒤, 현재 포인터의 다음 다음 노드를 연결해주면 된다.