목록2024/10/20 (1)

매일 조금씩

Leet code (Medium): 143. Reorder List - JAVA

처음엔 Stack이나 Deque로 풀어야하나 했지만, 공간복잡도가 O(N)이 나올것이기 때문에,좀더 효율적인 방법을 생각해야했다. 투 포인터를 사용하면 공간복잡도 O(1)로 문제를 해결할 수 있다.문제의 핵심은 다음과 같다.순방향과 역방향이 둘다 존재한다.그림으로 그려보았을 때, 리스트의 앞쪽 절반은 순반향, 뒤쪽 절반은 역방향이다.따라서, 다음과 같은 순서로 알고리즘을 진행한다.리스트의 중간 노드를 찾는다. (slow, fast 포인터를 사용. 이때, slow는 중간에 도달한다. 뒤쪽 절반의 첫 번째 노드)리스트 후반부를 역순으로 뒤집는다. (prev는 역순 리스트의 첫번째 노드. 즉, 원래 리스트의 마지막 노드)두 리스트 병합 (앞쪽 노드 next를 뒤쪽 노드로, 뒤쪽 노드 next를 앞쪽 노드로, ..
알고리즘/LinkedList 2024. 10. 20. 18:58
이전 Prev 1 Next 다음