N번째 노드 제거하기 (Linked List, Two pointer)

김민아·2023년 1월 28일
0

Remove Nth Node From End of List

19. Remove Nth Node From End of List

문제

  • 링크드 리스트에서 끝에서 n번째 노드를 삭제하는 문제이다. 단 한 번 순회하여야 하고, 전체길이를 모른채 n번째 노드를 삭제하기 위해 두 포인터를 이용한다.

테스트 케이스

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

풀이

  1. 첫 번째 포인터를 리스트의 시작으로 이동한다.
  2. 두 번째 포인터를 n만큼 이동한다.
  3. 첫 번째 포인터와 두 번째 포인터를 함께 이동시킨다.
  4. 두 번째 포인터가 리스트의 끝에 도달할 때까지 이동시키며, 첫 번째 포인터는 삭제할 노드의 직전 노드가 된다.
  5. 첫 번째 포인터가 가리키는 노드의 다음 노드를 삭제할 노드의 다음 노드로 변경한다.
  6. 리스트의 헤드 노드를 반환한다.
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  let dummy = new ListNode(0);
  dummy.next = head;
  let first = dummy;
  let second = dummy;

  for (let i = 0; i <= n; i++) {
    second = second.next;
  }

  while (second !== null) {
    first = first.next;
    second = second.next;
  }

  first.next = first.next.next
  return dummy.next;
};

0개의 댓글