[코딩테스트] 가장빠르게 역순 링크드리스트 만들기

 

문제 : 주어진 단일 연결 리스트를 역순으로 만들어라

 

예제:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

 

정말 유명하고 고전적이면서 간결한 문제이다. 기본적인 문제인 만큼 2가지 방법으로 풀 수 있다는 것을 알아두고 보자마자 2가지 방법으로 풀 수 있도록 연습하기를 권장한다. 재귀적인 방법과 반복문을 사용하는 방법 두 가지 모두를 알아보도록 하겠다. 이번 문제도 Leetcode에서 코딩을 작성하고 답변을 확인할 수 있다. (https://leetcode.com/problems/reverse-linked-list/)

 

참고로 제대로 풀었다면 공간 복잡도는 O(1)이 되어야 한다. 만약에 다른 보조 메모리를 사용하여 O(N)으로 풀었다면 O(1)으로 풀 수 있도록 생각해보도록 하자. 이번 글에서는 O(1)으로 푸는 방법만을 제시할 것이다.

 

노드 하나하나 방문을 하면서 현재 노드의 다음 노드를 이전 노드로 가르쳐주면 된다. 하지만 단일 연결 리스트 (singly linked list)이기 때문에 이전 노드 (previous node) 값을 알 수 없다는 문제에 직면할 것이다. 그렇기 때문에 이전 노드를 계속해서 저장해주고 다음 노드로 진행할 때마다 업데이트해줘야 하는 방법을 사용하도록 하자.

 

그리고 이번 문제의 목표는 반전한 노드의 첫 번째 노드를 반환해야하므로 현재 노드를 가르키는 전용 노드를 사용하도록 하자. 이렇게하면 마지막에 첫번재 노드를 반환하기만 하면 된다.

 

반복문을 사용한 코드:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        
        return prev;
    }

시간 복잡도는 O(N)이고 공간 복잡도는 O(1)이다. N은 연결 리스트의 길이이다.

 

 

재귀적인 코드:

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

 

재귀적으로 푸는 방법은 반복문으로 푸는 것보다 조금 더 어려울 수 있다. (조금 더 생각이 더러워진다고 표현할 수 있겠다). 생각에 꼬인다면 이미 반전돼있다고 생각하고 푸는 게 어쩌면 도움이 될 수도 있을 것이다. 주의해야 할 점은 길이가 2인 경우에 버그가 생기지 않도록 처리해줘야 한다는 것이다. 

 

위 코드의 시간 복잡도는 O(N)이고 공간 복잡도는 O(N)이다. 재귀적인 방법으로 풀었다면 왜 공간 복잡도가 연결 리스트 길이만큼 사용되는지 설명할 수 있어야 한다.

 

재귀 프로그래밍은 메서드 호출 스택을 사용하므로 그만큼의 공간이 사용되기 때문인 것을 언제나 명심하도록 하자. 우리가 아는 StackoverFlow에러가 메서드 호출 공간이 부족하면 발생하는 것이다. 이러한 단점 때문에 재귀 프로그래밍을 실 서비스에서 지양하는 곳이 많다. 

 

하지만 재귀적인 코드는 나중에 다른 문제를 풀 때 유용하게 사용될 수 있으므로 문제 풀 때는 유용하게 사용할 수 있으니 알아두면 피와 되고 살이 된다.

 

아직도 이해가 잘안가고 막히는 부분 이 있다면  youtube에서 설명을 보는 것을 추천한다.

 

이번 문제를 누워서 숨 쉴 정도로 쉽게 풀었다면 비슷한 유형의 문제인 부분 반전 문제를 풀어보길 추천한다. (https://leetcode.com/problems/reverse-linked-list-ii/)