[Leetcode] 19. Remove Nth Node From End of List

Leetcode

[Leetcode] 19. Remove Nth Node From End of List - JS

Wix 2024. 11. 7. 10:00

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-interview-150

1. 문제 분석

문제분석
--------------------
- 연결리스트 head가 주어지면, 끝에서 n번째 노드를 제거하여 연결리스트를 반환하라.

제한조건
--------------------
- sz는 연결리스트 속 노드의 갯수이다.
- 1 <= sz <= 30
- 0 < Node.val <= 100
- 1 <= n <= sz

2. 접근 방법

접근방법
--------------------
연결리스트 길이 구하기 위한 countHead 변수 추가

dummy 생성
dummy.next = head
prev = dummy

prev를 끝에서 n번째 까지 도달 (sz - n 까지)

curr = prev.next
prev.next = curr.next
curr.next = null;

dummy.next 반환

3. 코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var removeNthFromEnd = function(head, n) {
    let sz = 0;
    let countHead = head;
    while (countHead !== null) {
        countHead = countHead.next;
        sz++;
    }

    const dummy = new ListNode();
    dummy.next = head;
    let prev = dummy;

    for (let i = 0; i < sz - n; i++) {
        prev = prev.next
    }

    let curr = prev.next;
    prev.next = curr.next;
    curr.next = null;

    return dummy.next;
};

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

prev 변수를 선언하여 제거하려는 노드 이전 노드까지 접근한 뒤,

prev.next 포인터를 curr.next로 갱신하고 curr.next 포인터는 null로 초기화 하여

가비지 컬렉션에 메모리가 남지 않도록 한다.

5. 연결리스트 갯수 세지 않고 푸는 방법

연결리스트 갯수를 매번 문제 풀 때마다 세주고 있었는데, 이번 문제에서는 갯수를 세지 않아도 되는 방법도 같이 알아보자.

var removeNthFromEnd = function(head, n) {
    let res = new ListNode(0, head);
    let dummy = res;

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

    while (head) {
        head = head.next;
        dummy = dummy.next;
    }

    dummy.next = dummy.next.next;

    return res.next;    
};

res 값을 head 앞에 생성해준다.

head는 제거하려는 위치인 n만큼 이동시켜준다.

head가 마지막에 도달할 때 까지 dummy와 함께 이동시켜준 뒤,

마지막에 도달했을 때, dummy의 next를 그 다음으로 갱신해준다.

head = [1, 2, 3, 4, 5] n = 2 일 때,

[1, 2, 3, 4, 5]

d h

head 마지막에 도달시