[알고리즘] Leetcode. Remove Nth Node From End of List

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

연결리스트 head과 n이 주어지고 끝에서 n번째 노드를 삭제하고 head를 return 하라

 

Example 1:

---

방법 1.

 

처음 생각한 방법

2개의 포인터가 필요함. p1(포인터1)은 head부터 시작, p2는 head.next부터 시작

리스트 길이를 계산하고 (리스트 길이 - n) 만큼 이동해  p1.next는 지울 노드가 되고 p2는 지울 노드를 가리킨다.

 

고려해야 할 코너케이스

1. n이 length와 같을 때

: 이 경우에는 p1 head 자체를 지워야한다. 

 

2. length가 1일 때

: 위 첫 번째 케이스와 같은 케이스로 처리할 수 있다.

var removeNthFromEnd = function(head, n) {
    let temp = head;
    let p1 = head.next;
    let p2 = head;
    let length = 0;

    while (temp.next) {
        length++;
        temp = temp.next;
    }
    
    // 만약 n이 node의 length와 길이가 같다면 head를 삭제
    if (length === n - 1) {
        head = head.next;
        return head;
    }

    for (let i = 0; i < (length - n); i++) {
        p1 = p1.next;
        p2 = p2.next;
    }

    p2.next = p1.next;
    
    return head;
};

풀면서도 별로라고 생각했는데 풀고나서도 보니 별로다.

 

---

방법 2.

dummy를 사용하면 코너 케이스를 쉽게 해결할 수 있다고 한다. (👏👏👏) 

head를 복사할 때 dummy = head 이렇게 하는 게 아니라 dummy.next = head 이렇게 하면 length가 1일 때 케이스를 생각하지 않아도 된다. 

 

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode();
    dummy.next = head;
    let p1 = dummy;
    let p2 = dummy;
    
    for (let i = 0; i < n; i++) {
        p1 = p1.next;
    }
    
    while (p1.next) {
        p1 = p1.next;
        p2 = p2.next;
    }
    
    p2.next = p2.next.next;
    
    return dummy.next; 
}

 

만약 length = 5, n = 2 라면

🤍🤍🤍💛🤍 (노란 하트는 지워야 할 노드)

 

p1을 n만큼 옮겨간다.

🤍🤍💚💛🤍 초록색 위치에 p1이 위치해있다.

 

p1, p2를 p1의 next가 null이 될 때까지 이동하면 2번을 이동하게 되는데

🤍🤍💙💛💚 p2의 next 노드가 지워야 할 노드의 위치가 된다.

p2.next(💛) = p2.next.next (💚) 

 

결과

🤍🤍💙💚

 

---

방법 3.

dummy를 쓰지 않는 방법

var removeNthFromEnd = function (head, n) {
    // Two pointers - fast and slow
    let slow = head;
    let fast = head;
    // Move fast pointer n steps ahead
    for (let i = 0; i < n; i++) {
        if (fast.next === null) {
            // If n is equal to the number of nodes, delete the head node
            if (i === n - 1) {
                head = head.next;
            }
            return head;
        }
        fast = fast.next;
    }
    // Loop until we reach to the end.
    // Now we will move both fast and slow pointers
    while (fast.next !== null) {
        slow = slow.next;
        fast = fast.next;
    }
    // Delink the nth node from last
    if (slow.next !== null) {
        slow.next = slow.next.next;
    }
    return head;
};

방법 2에서 dummy를 사용하면 다른 케이스를 생각하지 않아도 돼서 좋지만 공간을 더 사용한다는 단점이 있는데 그걸 보완해준 방법인 것 같다. 

 

---

 

참고한 블로그

https://www.fwantastic.com/2021/01/leetcode-19-remove-nth-node-from-end-of.html

[Leetcode] #19. Remove Nth Node From End of List 뒤에서 N번째 노드 지우기

https://redquark.org/leetcode/0019-remove-nth-node/

LeetCode #19 - Remove Nth Node From End Of List