Linked List 에서 중간 노드 최대한 빨리 찾기
문제 설명
간단하고 재밌는 문제다.
"단일 LinkedList 에서 중간 노드를 가장 효율적으로 찾아라."
아주 간단한 아이디어만 떠올리면 되는데 처음에는 잘 떠오르지 않았던 문제다.
아래 구현된 코드의 방법보다 빠른 알고리즘이 있나? (없을 듯...)
- 조건
- tail 노드를 직접 접근하는 메소드는 제공하지 않는 상황.
- LinkedList 의 size 를 알 수 있는 메소드도 제공하지 않는 상황(즉, 노드 갯수 모르는 상황)
- 노드 간 이동은 오로지 list head 부터 link 를 따라가는 방법 밖에 없음
- Collection 및 stl 을 사용하지 말 것 - 힌트
- 시간복잡도는 O(N)이지만 정확하게는 O(N/2)
Source Code
아래 코드의 findMiddle() 메소드 참고.
class SingleList { Node head; private class Node { private int data; Node next = null; Node(int data) { this.data = data; } public int getVal() { return this.data; } } public void findMiddle() { Node f = head; Node s = head; while(f != null && f.next != null) { s = s.next; f = f.next.next; } System.out.println(s.getVal()); } public void add(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } public void printAll() { Node node = head; while(node != null) { System.out.print(node.getVal() + "->"); node = node.next; } System.out.println("null"); } } public class ListMiddle { public static void main(String[] args) { SingleList s = new SingleList(); s.add(5); s.add(4); s.add(3); s.add(2); s.add(1); s.printAll(); s.findMiddle(); } }
수행 결과
$> java ListMiddle 1->2->3->4->5->null 3