해당 포스팅은 릿코드 19번 Remove Nth Node From End of List 풀이를 다룬다. 문제 링크
코드는 Javascript로 작성했으며 링크드리스트와 투포인터로 풀이하였다.

문제

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

링크드리스트의 헤드가 주어지면 링크드리스트 끝에서 n번째 노드를 제거하고 헤드를 반환하라.

예제

n이 2이므로 링크드리스트의 끝에서 2번째인 노드 4를 제거한 후 head인 [1,2,3,5]를 반환한다.

풀이

풀지 못했던 문제라 다른 사람들이 푼 풀이를 공유하고자 한다!

해당 문제는 투포인터로 풀이해야 하는 문제다.

front는 링크드리스트의 마지막 노드를 확인하기 위해서 사용되고, back은 링크드리스트의 끝에서 n번째 노드를 확인해 삭제하는 데 사용된다.

로직

• 먼저 링크드리스트의 앞에 root 노드를 하나 추가한다. root 노드를 추가하는 이유는 링크드리스트의 원소 개수가 1개이고 n이 1일 때와 같은 여러 코너 케이스를 해결하기 위함이다.

• 투 포인터 front, back을 root노드로 설정한다.

• 먼저 front를 n만큼 앞으로 이동시킨다. 이후 back이 링크드리스트의 끝에서 n번째 노드를 가리키게끔 해준다.

• front가 null이 될 때까지 투 포인터 front와 back을 앞으로 이동시킨다.

• back.next는 끝에서 n번째 노드이다. 따라서 back.next를 back.next.next로 바꾸자. 그러면 back.val은 back.next.next를 가리키므로 끝에서 n번째 노드가 삭제되게 된다.

전체 코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    const root = new ListNode(0);
    root.next = head;
    
    let front = root;
    let back = root;
    
    while (n >= 0) {
        front = front.next;
        n--;
    }
    
    while (front) {
        front = front.next;
        back = back.next;
    }

    back.next = back.next.next;
    return root.next;
};