[Leetcode 234] Palindrome Linked List - 스택,데크,러너

https://leetcode.com/problems/palindrome-linked-list/

Palindrome Linked List - LeetCode

 

Problem

연결 리스트가 팰린드롬 구조인지 true/false를 반환해라.

 

input = [1,2,2,1]

output = true

 

 

전략 1 : 스택을 이용한 풀이

 

팰린드롬을 판별하기 위해서는 앞 뒤로 판별 가능한 자료구조로 풀이를 진행할 수 있다. 그 중 스택 자료구조로 먼저 연결리스트를 스택에 복사해 넣은 다음, 다시 연결리스트를 앞에서부터 이동하면서 값을 조회하고 , 스택은 pop()을 호출하며 뒤에서 부터 값을 빼고 비교하는 식으로 풀이가 가능하다.

 

public boolean isPalindrome(ListNode head) {
    Stack<Integer> st = new Stack<>();
    ListNode node = head;
    while (node != null) {
        st.add(node.val);
        node = node.next;
    }

    while (head != null) {
        if (head.val != st.pop()) {
            return false;
        }
        head = head.next;
    }
    return true;
 }

 

하지만 스택 자료형은 스레드 안전성 문제 때문에 더이상 쓰이지 않는다. 그래서 다음 풀이와 같은 전략을 사용한다.

 

전략 2 : Deque를 이용한 풀이

아까 스택 풀이같은경우 연결리스트를 모두 넣고 다시 모두 빼면서 비교하는 식으로 진행했다. 이 자료형은 앞을 빼지 못하지만 이번 Deque를 활용한 풀이는 앞 뒤를 같이 빼면서 런타임 시간을 좀 더 줄일 수 있다. 

 

위: Deque 풀이 아래: Stack 풀이

 

 

Deque는 인터페이스 이며, 구현체는 LinkedList와 ArrayDeque가 있다. 이중 앞 뒤를 뺄 때 시간 복잡도가 O(1)인 LinkedList를 구현체로 사용하면 된다.

 

public boolean isPalindrome(ListNode head) {
    Deque<Integer> deque = new LinkedList<>();

    ListNode node = head;
    while (node != null) {
        deque.add(node.val);
        node = node.next;
    }

    // 데크가 모두 비거나(짝수개수) 1개 이하(홀수 개일때)가 될때까지 비교
    while(!deque.isEmpty() && deque.size()>1){
        if(deque.pollFirst() != deque.pollLast()){
            return false;
        }
    }
    return true;
}

 

 

전략 3 : 러너 기법을 활용한 풀이

아무런 자료 구조를 사용하지 않고 단지 러너 기법을 활용하면 런타임 시간이 더 짧게 풀이를 할 수 있다. 이는 팰린드롬 연결리스트 문제의 제대로 된 풀이법이라 한다.

 

러너기법이란, 연결리스트를 순회할 때 2개의 포인터를 동시에 사용한다. 한 포인터가 다른 포인터보다 앞서게 한다. 빠른 러너는 두 칸씩 건너뛰고 느린 러너는 한 칸씩 이동시킨다. 이때 빠른 러너가 연결리스트의 끝에 도달하면 느린러너는 연결리스트의 중간 지점을 가르키게 된다. 이 같은 방식을 사용하여 중간 위치를 찾아내면 전체 길이를 알아낼 수 있고, 여기서 부터 값을 비교하거나 뒤집기를 시도할 수 있는 연결리스트의 대표적 풀이 기법이다.

 

다음은 러너 기법을 사용해서 뒤집기를 시도하는 풀이이다.

 

public boolean isPalindrome(ListNode head) {
    ListNode fast = head, slow = head;

    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }

    // 홀수 개 일때 느린 러너가 한 칸 더 앞으로 가도록 처리
    if (fast != null){
        slow = slow.next;
    }

    // 중간에 도달한 느린 러너를 기준으로 하여 역순 연결리스트를 만든다.
    ListNode rev = null;
    while(slow != null){
        ListNode next = slow.next;
        slow.next = rev;
        rev = slow;
        slow = next;
    }

    while(rev != null){
        if(rev.val != head.val)
            return false;

        rev = rev.next;
        head = head.next;
    }

    return true;

}

 

 

Fast 러너는 Slow러너가 연결리스트의 중간까지 오는 데 도와주는 도구일 뿐이다.

 

 

그리고나서 홀수 개임을 빠른 러너가 판단하고 느린 러너를 한칸 더 앞으로 이동하도록 처리한다. 다음 중간 러너를 통해 역순의 연결리스트를 새롭게 만든다. 다음은 while문이 한 사이클 지날때마다 변화된 그림이다.

 

 

 

자료구조를 사용하지 않으니 정말 빠르다.

 

 

 

 

레퍼런스

 

자바 알고리즘 인터뷰 with 코틀린