단순 연결리스트 역순으로 뒤집기

단순 연결리스트에 대한 개념이 부족해서 전에는 풀지 못했던 문제였고, 공부를 해보았다. 한쪽 방향으로만 연결되어있다는 특징을 최대한 활용해야하는 문제이다.

일반적인 배열이나 ArrayList라면 인덱스로 간단하게 바꿀 수 있다. 이중 연결리스트도 오버헤드가 좀 들지만 비교적 간단하게 가능하다. 하지만 단순 연결리스트는 생각을 좀 해야하는데, 처음에 생각했던 방법은 모든 요소를 스택에 집어넣어서 하나씩 빼며 리스트를 새로 생성하는 것이었다. 하지만 이 방법은 리스트의 크기만큼의 메모리가 필요하기 때문에 규모가 커지면 효율적이지 못하다. 시간적으로도 선형 탐색을 두번해야한다는 점에서 그 단점을 알 수 있다. 그래서 추가메모리를 최대한 줄이고 탐색 시간도 줄이기 위해서는 다음과 같이 하면 된다.

핵심은 새로운 리스트의 맨 끝을 나타내는 null 값이 들어있는 노드를 생성하고, 기존 리스트를 순회하면서 가장 첫번째 노드를 앞에 붙인다는 것이다. 이렇게하면 새노드->next는 새로운 리스트의 맨 앞(가장 처음이라면 null 값이 들어있는 노드)를 가리키게 되어 결과적으로 역순이 되는 것이다. 소스는 다음과 같다.

Node reverse(Node head) {
    Node p, q, r;
    p = head;
    q = null;
    while(p!=null) {
        r = q;
        q = p;
        p = p.next;
        q.next = r;
    }
    return q;
}

간단한 코드인데 그때는 왜 못했을까... 더 열심히 공부해야겠다.