연결 리스트에서 노드 삭제

Source: Dev.to

문제 링크 - https://leetcode.com/problems/delete-node-in-a-linked-list/
이 문제는 처음 보면 불가능해 보이는 면접 질문 중 하나입니다.
보통 연결 리스트에서 노드를 삭제하려면 이전 노드에 접근해야 합니다.
하지만 이 문제에서는 삭제해야 할 노드만 주어지고, 리스트의 head는 주어지지 않습니다.
그렇다면 어떻게 삭제할 수 있을까요?
트릭을 이해해 봅시다.

단일 연결 리스트에서 노드를 삭제하는 함수를 작성하세요.
리스트의 head는 주어지지 않고, 대신 삭제해야 할 노드만 주어집니다.

입력:
4 -> 5 -> 1 -> 9

node = 5

출력:
4 -> 1 -> 9

보통 노드를 삭제할 때는 다음과 같이 합니다.
prev.next = node.next

하지만 여기서는

• prev가 없음
• head가 없음

따라서 일반적인 삭제 방법은 사용할 수 없습니다.
현재 노드를 직접 삭제할 수는 없지만, 마치 존재하지 않았던 것처럼 만들 수 있습니다.

예시:
4 -> 5 -> 1 -> 9

삭제해야 할 노드: 5

노드 5를 제거하는 대신, 다음 노드의 값을 복사합니다.
4 -> 1 -> 1 -> 9

그 다음, 복사한 다음 노드를 제거합니다.
4 -> 1 -> 9

원래 값 5가 사라졌습니다.
임무 완수.

1. 다음 노드의 값을 현재 노드에 복사한다.
2. 다음 노드를 건너뛴다.
3. 현재 노드는 마치 삭제된 것처럼 동작한다.

문제에서 주어진 노드가 꼬리 노드가 아니라는 것이 보장되므로, 항상 다음 노드가 존재합니다.

4 -> 5 -> 1 -> 9

node = 5

현재 노드:
5

다음 노드:
1

다음 노드 값을 복사한다.
node.val = node.next.val

리스트는 다음과 같이 된다.
4 -> 1 -> 1 -> 9

다음 노드를 건너뛴다.
node.next = node.next.next

리스트는 다음과 같이 된다.
4 -> 1 -> 9

완료.

class Solution {
    public void deleteNode(ListNode node) {

        ListNode cur = node.next;

        node.val = cur.val;
        node.next = cur.next;
    }
}

class Solution {
    public void deleteNode(ListNode node) {

        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Metric

Complexity

Time Complexity
O(1)

Space Complexity
O(1)

우리는 실제로 주어진 노드를 삭제하는 것이 아니라,
그 값을 다음 노드의 값으로 덮어쓰고, 다음 노드를 체인에서 제거합니다.
그 결과 연결 리스트는 목표 노드가 삭제된 것과 동일하게 동작합니다.

핵심 트릭은 이전 노드에 접근할 수 없으므로 직접 삭제가 불가능하다는 점을 인식하고,
대신 현재 노드를 다음 노드로 변형하고 그 다음 노드를 삭제하는 것입니다.

이는 면접에서 자주 등장하는 가장 우아한 O(1) 연결 리스트 트릭 중 하나이며,
이 문제는 중요한 면접 교훈을 가르칩니다:
때로는 문제에서 직접 요구하는 일을 수행하는 것이 아니라,
똑똑한 관찰을 통해 동일한 최종 상태를 얻는 것이 해답이 될 수 있습니다.