팁
이동하며 요소를 추가 / 삭제를 할 때 사용하는 자료구조이다.
에디터와 같은 편집기 문제에 사용된다.
STL의 list에서의 메서드가 반환하는 이터레이터 위치를 주의하자.
insert인 경우 새로 넣은 요소들의 첫 번째 위치를 가리키는 이터레이터를 반환하고
erase인 경우 삭제한 요소의 다음의 요소를 가리키는 이터레이터를 반환한다.
알면 좋은 것들
문제
원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법은?
정답
동일한 노드가 나올 때 까지 계속 다음 노드로 가면 됨.
공간복잡도 O(1), 시간복잡도 O(N)
문제
중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법은?
정답
각각의 리스트의 길이를 먼저 구함.
(긴 리스트의 길이 - 짧은 리스트의 길이) 만큼 긴 리스트를 먼저 앞으로 이동시켜서
짧은 리스트의 길이와 동일한 출발점에 위치시킨다.
그 후 만날때까지 두 리스트에서 한칸씩 번갈아 이동하면 된다.
공간복잡도 O(1), 시간복잡도 O(A+B)
정답2
A리스트를 먼저 전체 순회하며 노드안에 flag를 표시한다.
B리스트를 순회하며 flag를 발견할때까지 한칸씩 이동한다.
공간복잡도 O(N), 시간복잡도 O(A+B)
문제
주어진 연결 리스트 안에 사이클이 있는지 판단하라.
정답
Floyd's cycle-finding 알고리즘을 사용한다.
공간복잡도 O(1), 시간복잡도 O(N)
Floyd's cycle-finding 알고리즘 :
한 칸씩 이동하는 커서와 두 칸씩 이동하는 커서를 동일한 시작점에서 출발시키면 사이클이 내부에 존재할 때는 반드시 두 커서가 만나게 되고 그렇지 않다면 끝에 도달한다.
