𝗗𝗲𝗹𝗲𝘁𝗲 𝘁𝗵𝗲 𝗠𝗶𝗱𝗱𝗹𝗲 𝗡𝗼𝗱𝗲 𝗼𝗳 𝗮 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁
단일 연결 리스트에서 중간 노드를 제거해야 합니다. 중간 노드는 0-기반 인덱스를 기준으로 ⌊n / 2⌋번째 노드입니다.
효율적으로 해결하는 방법은 다음과 같습니다.
전략
두 개의 포인터를 사용하여 단 한 번의 순회로 중간 지점을 찾습니다.
- 한 번에 한 단계씩 이동하는 slow 포인터를 사용합니다.
- 한 번에 두 단계씩 이동하는 fast 포인터를 사용합니다.
- fast 포인터가 끝에 도달하면, slow 포인터는 중간에 위치하게 됩니다.
- slow 포인터의 이전 노드를 추적하기 위해 세 번째 포인터를 유지합니다.
로직
- 예외 상황을 처리합니다. 리스트에 노드가 하나만 있다면 null을 반환합니다.
- slow와 fast 포인터를 head에서 초기화합니다.
- fast 포인터는 두 단계, slow 포인터는 한 단계씩 이동합니다.
- slow 포인터보다 한 단계 뒤에 머물도록 prev 포인터를 업데이트합니다.
- 루프가 종료되면, prev 노드를 slow의 다음 노드에 연결합니다. 이렇게 하면 중간 노드가 건너뛰어집니다.
복잡도
- 시간 복잡도: O(n). 리스트를 한 번 순회합니다.
- 공간 복잡도: O(1). 세 개의 포인터만 사용합니다.
PHP 구현
function deleteMiddle(ListNode $head): ?ListNode { if ($head->next == null) { return null; }
$slow = $head;
$fast = $head;
$prev = null;
while ($fast !== null && $fast->next !== null) {
$prev = $slow;
$slow = $slow->next;
$fast = $fast->next->next;
}
$prev->next = $slow->next;
return $head;
}
Source: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1