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