[문제13][LeetCode] 234. 팰린드롬 연결 리스트

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

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

* A palindrome is a sequence that reads the same forward and backward.

Example 1:
Input: head = [1,2,2,1]
Output: true

Example 2:
Input: head = [1,2]
Output: false

Constraints:
The number of nodes in the list is in the range [1, 10⁵]
0 <= Node.val <= 9

 

접근 방법 

1. 시간복잡도: O(N) 

주어진 문제에서 노드의 범위가 10⁵이므로 O(N²)인 자료구조로 풀이할 시 시간 초과가 날 가능성이 높습니다. 따라서 O(logN), O(N) 또는 O(N*logN)으로 풀 수 있는 방법을 고려했습니다. 풀이에 사용할 수 있는 여러 자료구조가 있겠지만, 저는 가장 먼저 스택이 떠올랐으므로 스택을 사용할 예정입니다.

 

2. head로 받은 원소들을 어떻게 받아서 처리할 것인가?

public boolean isPalindrome(ListNode head) {
     ...   
}

➡ head의 원소들을 스택에 바로 넣도록 구현하였습니다.

* Deque(double-ended queue) 기반 Stack 구현 예정

 Deque<Integer> dq = new ArrayDeque<>();
 ...
 while (node != null) {
    dq.add(node.val);
    node = node.next;
}

 

3. dq에 있는 원소가 다 없어질 때까지 while문을 돌면서, dq의 가장 마지막 원소와 현재 위치의 node의 값을 비교하면서 다르면 false를 반환합니다.

 

코드 구현

실패 코드

import java.util.*;

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

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

        node = head;

        while (!stack.isEmpty()) {
           if (!stack.pop().equals(node.val)) { 
                return false; 
            }
            node = node.next; 
        }
        return true;  
    }  
}

 

디버깅 

IDE 툴을 사용하지 않으므로 System.out.println()을 사용해서 추적해 보겠습니다.

 

원인

pop()은 Deque에 존재하지 않습니다.😂 ㅎㅎㅎㅎㅎㅎ..

 

성공 코드

import java.util.*;

class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<Integer> dq = new ArrayDeque<>();

        ListNode node = head;
        while (node != null) {
            dq.add(node.val);
            node = node.next;
        }
        
        node = head;
        
        while (!dq.isEmpty()) {
           if(dq.removeLast() != node.val) {
               return false;
           }
            node = node.next; 
        }
        return true;  
    }  
}

 

배우게 된 점

1. head로 받은 원소들을 어떻게 받아서 처리할 것인가?

따로 특정 자료구조로 받지 않고 바로 원하는 자료구조에 넣을 수 있습니다.

 

2. Deque(double-ended queue) 기반 Stack 구현

Stack 클래스는 스택 자료구조를 구현하기 위해 사용되지만, 성능 면에서 Deque 인터페이스와 ArrayDeque 클래스를 사용하는 것보다 떨어집니다. 

Deque<T> q = new ArrayDeque<>();

 

3. 자료형을 사용할 때 사용법을 알아보고 사용할 것

원소 삽입

- 앞

addFirst()
offerFirst()

- 뒤

addLast()
add()
offerLast()
offer()

 

원소 제거

- 앞
remove()
removeFirst()
poll()
pollFirst()
- 뒤
removeLast()
pollLast()

 

원소 확인 (제거 X)

- 앞
getFirst()
peek()
peekFirst()
- 뒤
getLast()
peekLast()

 

4. node = head;

node = head;를 하는 이유는 첫 번째 단계에서 node가 리스트의 끝까지 이동했기 때문에, 두 번째 단계를 수행하기 위해 node를 다시 리스트의 시작 지점으로 되돌려 놓아야 하기 때문입니다.