[leetcode] Palindrome Linked List

문제 설명

• 문제 링크
• singly linked list가 주어질 때, Palindrome 여부를 return 한다.
  • linked list의 값을 앞으로 읽든 뒤로 읽든 같다면 Palindrome이라고 할 수 있다.
• 제약 조건
  • linked list 길이: [1, 10^5]
  • linked list에 있는 값의 범위: 0 <= Node.val <= 9

풀이

풀기 전

• 앞으로 읽든 뒤로 읽든 값이 같다는 건 가운데를 기준으로 대칭이라는 의미이다. 그래서 모든 값을 일렬로 세운 뒤 가운데를 기준으로 왼쪽, 오른쪽으로 이동하며 값이 같은지 확인하면 된다.
• linked list 끝까지 가서 값들을 저장하면 linked list의 길이와 가운데 지점을 알 수 있게 된다. 그 후 대칭인지 확인하면 된다.
• 시간복잡도는 O(linked list 길이)이다. 공간복잡도도 동일하다. linked list에 있는 값들을 따로 저장하지 않고, 주어진 linked list로만 풀면 메모리를 좀 줄일 수 있긴 하다.

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> nums = new ArrayList<Integer>();
    
    	// linked list 순회하면서 nums에 모든 값들을 저장한다.
        ListNode now = head;
        while (now != null) {
            nums.add(now.val);
            now = now.next;
        }
        
        // 맨 앞의 값과 맨 뒤의 값을 시작으로, 대칭인지 확인한다.
        int size = nums.size();
        for (int i=0; i<size/2; i++) {
            if (nums.get(i) != nums.get(size-i-1))
                return false;
        }
        
        return true;
    }
}

푼 후

• 이번 문제는 간단했다. daily 문제의 난이도가 일정하지는 않은 거 같다.
• 다른 사람들 코드를 보니 값들을 추가로 저장하지 않고 주어진 linked list로만 해결하는 방식이 있었다. 방식은 동일하지만 linked list의 가운데 지점을 찾고 비교해나간다는 점이 달랐다.
  • 그럼 linked list의 가운데는 어떻게 찾을 수 있을까. head를 가리키는 포인터 a, b를 만든 뒤, a는 한 칸씩(a = a.next) 옮기고 b는 두 칸씩(b = b.next.next) 옮긴다. b가 끝에 다다르면 a는 중간에 위치하게 된다. a와 b를 이용해서 대칭을 확인하면 된다.
  • 그런데 주어진 linked list에는 단일(singly) 연결 리스트이므로 이전 노드를 알 수 없다. 그래서 대칭을 확인하려면 a가 있는 가운데 지점에서 왼쪽편에 있는 값들을 역으로 뒤집어야 한다. 그 후 a 오른쪽에 있는 값들과 비교할 수 있다.
  • 위 방식은 메모리를 덜 사용하긴 하지만, 코드가 복잡해지는 걸 감수할만큼은 아니라는 생각이 들었다.