링크 된 목록의 요소

Question

누군가 설명해주세요. Java에서 링크 된 목록의 중간 요소를 어떻게 확인합니까?

나는 그것을 봤지만 코드 작성 방법에 대한 간단한 설명을 찾을 수없는 것 같습니다.

Answer 1

LinkedList이므로 첫 번째 (및 유일한) 통과 이후까지 크기를 알 수 없습니다. 중간 요소를 찾으려면 두 가지를 알아야합니다. 어떤 인덱스가 중간에 있으며, 그 인덱스에서 요소의 값은 무엇입니까? 가운데 색인을 찾는 것은 쉽습니다. 단지 하나의 목록을 통과시키고, 얼마나 많은 노드가 있는지에 대한 카운터를 유지하십시오. 이렇게하면 LinkedList를 한 번만 통과 할 수 있으므로 별도의 데이터 구조 (ArrayList)의 각 요소를 추적해야합니다. 완료되면 카운터의 반을 중간 색인을 찾아 해당 색인에 ArrayList 요소를 반환합니다.

의사 코드는 다음과 같습니다 : 물론

int count 
ArrayList elements 

for each node in LinkedList: 
    count++ 
    elements.append(node) 

middleIndex = count/2 
middleElement = elements.getIndex(middleIndex) 

return middleElement 

, 단일 중간 요소가없는 곳의 경우 알아서해야합니다.

Answer 2

LinkedList<String> list = new LinkedList<>(); 
list.add("foo"); 
list.add("bar"); 
list.add("baz"); 
String middle = list.get(list.size()/2); 
System.out.println(middle); // bar 

get 통화 중에 목록의 절반을 통과하게된다 middle을 할당 할 수 호출.

의견에서 지적한 바와 같이 중간은 LinkedList에서 작동하는 최악의 장소입니다. ArrayList과 같은 다른 변형을 사용해보십시오.

Answer 3

나는 이것이 가능한 인터뷰 질문 목록에서 볼 수있는 일종의 트릭 질문이라고 생각합니다.

하나의 해결 방법은 두 단계의 단계를 거치고 하나의 단계를 수행하는 두 가지 포인터를 갖는 것입니다.

한 번에 두 단계를 수행하는 포인터가 목록의 끝에 도달하면 한 단계 만 수행하는 포인터가 중간에 위치합니다.

나는이 연습은 정말로 유용 의심 ..

행운을 빕니다!