💬 문제
연결 리스트의 첫 번째 노드 head
뒤에서 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) {
let newHead = new ListNode(0, head);
let nPrev = newHead;
for (let i = 0; i < n; i++)
head = head.next;
while (head) {
head = head.next;
nPrev = nPrev.next;
}
nPrev.next = nPrev.next.next;
return newHead.next;
};뒤에서 n번째인 노드를 파악하기 위해
head는 마지막까지 이동, nPrev는 head와 n만큼 떨어진 곳까지 이동해야 함
우선 head를 n만큼 이동시키고, nPrev는 head 이전에서 시작하기 위해
새로운 만들어 head 앞에 연결시킨 노드를 가리킴
head가 끝날 때까지 함께 이동한 후 뒤에서 n+1인 위치에 도착한
nPrev의 next를 next의 next로 변경
미리 저장해두었던 head를 반환
📌 결과
Accepted
Runtime 47ms (Beats 93.47%)
Memory 50.62MB (Beats 35.41%)
📚 러닝 포인트
역시 역순으로 무언가를 확인하려면 투 포인터를 사용하는 것이다! 이제 조금 눈치를 챈 것 같아서 다행이다. 일단 이번 문제에서는 n번째 노드 제거를 위해서는 n+1번째, 즉 n번째 노드의 이전 노드를 수정해야 한다. 따라서 두 포인터 head와 nPrev는 n만큼 차이(둘 사이에 n개의 노드가 존재)해야 한다. 그래서 먼저 head를 n번 이동시키는데, 여기서 주의할 점이 있었다.
연결 리스트의 노드가 하나일 때, n이 연결 리스트의 크기여서 첫 번째 노드를 삭제해야할 때 nPrev가 head에서부터 시작한다면 둘 사이에 n만큼의 거리를 벌릴 수가 없었다. (그러려면 head가 n+1번 이동해야하고, null 참조 발생...) 따라서 head 보다 한칸 앞에서 시작할 필요가 있었고, 그를 위해 newNode를 만들어 head를 next로 연결시켜주었다. 덕분에 해결은 했지만, 새 노드를 만들지 않고 예외처리를 통해 해결하는 방법도 찾았다.
var removeNthFromEnd = function(head, n) {
if (head.next === null)
return null;
let curr = head;
let nPrev = head;
for (let i = 0; i < n; i++)
curr = curr.next;
if (curr === null)
return head.next;
curr = curr.next;
while (curr) {
curr = curr.next;
nPrev = nPrev.next;
}
nPrev.next = nPrev.next.next;
return head;
};노드가 한 개일 때를 가장 먼저 예외처리한다. 다른 노드를 반환할 필요없이 null을 반환하면 된다. 이후 똑같이 curr를 n만큼 이동시키고 (여기서는 head를 반환할 것이기 때문에 다른 포인터를 이동시킴) 그 결과 curr이 마지막 노드를 지났다면 이는 즉 첫 번째 노드를 삭제해야 한다는 의미다. 따라서 그 경우 바로 head의 next를 반환해버린다. 이후로는 똑같다. 간단한 문제라도 이런 저런 방법으로 구현해보는 것도 재밌다. 효율이 얼마나 다른지 알아보고 싶기는 하지만 이 리트코드가 워낙 제출할 때마다 같은 코드라도 극과 극의 결과를 보여줘서... 그 부분은 아쉽다.
