싱글 링크드리스트 삭제하기

싱글 링크드 리스트에서 현재 노드 cur 를 삭제하려면 다음 두 단계로 수행할 수 있음:

 

 

1. cur 의 이전 노드 prev 와 next 노드를 찾는다:

 

 

2. prev를 cur의 next 노드로 연결: 

 

첫 번째 단계에서는, 우리는 prev와 next 를 알아내야 함. 그 다음은 cur reference를 사용하여 쉽게 찾을 수 있음.

그러나, 우리는 평균 O(N) 시간이 걸리는 prev를 찾기 위해 헤드 노드에서 링크드리스드를 순회해야 한다.

여기서 N은 링크드리스드의 길이이다. 따라서 노드를 삭제하는 데 걸리는 시간은 O(N)이 된다.

포인터를 저장하기 위해 일정한 공간만 필요하기 때문에 공간 복잡도는 O(1)이다.

 

 

https://leetcode.com/explore/learn/card/linked-list/209/singly-linked-list/1289/

Account Login - LeetCode