Linked List Simple Question

1. Circular Linked List 에서 임의의 Node 하나가 주어졌을 때, 이 List의 길이를 구하는 가장 효율적인 방법?

 

환영 링크드 리스트는 일반 링크드 리스트와 다르게 마지막에 있는 데이터의 next 주소값이 list의 front에 연결되어 있는 환영적인 구조이다. 따라서 임의의 노드가 주어졌을 때, 노드를 돌면서 같은 Node가 나올 때까지 list를 돌면 O(N)만에 구할 수 있을 것이다. 이때 값만 비교하는게 아니라 prev, next 주소값도 동일한 경우를 찾아야 할 것이다.

 

2. 중간에 만나는 두 LinkedList의 시작점이 주어졌을 때, 만나는 지점을 구하는 방법?

 

우선 두 list의 길이를 각각 구한다. 그 후 짧은 리스트를 두 리스트의 차이만큼 뒤로 밀고 길이를 맞춘다.