[75 LeetCode] 46 - Remove Nth Node From End of List

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Remove Nth Node From End of List - LeetCode

# 풀이 1

내가 생각한 풀이는 정직하게 마지막까지 간 후 뒤에서 n번째 노드의 prev와 next를 연결시켜주는 방식이다.

var removeNthFromEnd = function(head, n) {
  const arr = [];

  let cur = head;
  let prev = null;
  let i = 0;
  while (cur) {
      arr[i++] = cur;
      cur = cur.next;
  }
  if (n === arr.length) return head.next;

  prev = arr[arr.length - n - 1];
  prev.next = prev.next.next;

  return head;
};

# 풀이 2

A A A A A C B B B

뒤에서부터 N번째노드인 C를 구하려면, 리스트의 마지막과 C까지의 간격이 N이라는 것을 이용하면 된다.
슬라이딩 윈도우처럼 간격 N짜리 윈도우를 만든 후 그 윈도우를 끝까지 밀어주면, head가 가리키는 곳이 바로 타겟이 된다.

A A A A A C B B B
H --- T
  H --- T
    H --- T
      H --- T
        H --- T
          H --- T

 

var removeNthFromEnd = function(head, n) {
    if(!head.next) return null

    let tail = head;
    let remove = head; 
    let dummy = new ListNode(-1, head);
    let prev = dummy;

    // 윈도우를 만들어준다.
    while(n--) {
        tail = tail.next
    }

    // tail을 끝까지 밀어준다.
    // 여기선 위 그림과는 살짝 다르게 head가 dummy부터 시작, tail은 null까지 진행하도록 구현되었다.
    while(tail) {
        tail = tail.next;
        remove = remove.next;
        prev = prev.next;
    }

    prev.next = remove.next
    return dummy.next; 
};