234. Palindrome Linked List

2026-03-27
leetcode
리트코드 234번 풀이

문제

Palindrome Linked List

풀이

아이디어

싱글 연결 리스트가 팰린드롬인지 확인하는 문제이다. 팰린드롬을 확인하는 방법은 크게 2가지가 될 것 같은데, 첫번째는 직접 뒤집어서 확인하는 방법, 두번째는 양 끝에 포인터를 두고 안쪽으로 이동하면서 확인하는 방법이다. 그런데 문제에 등장하는 싱글 연결 리스트로는 두 방법 모두 불가능하기 때문에 가능한 형태인 배열로 변환해서 풀이했다.

연결 리스트를 순회하면서 값을 배열에 넣는다. 그리고 팰린드롬을 판단하는 두번째 방법인 투포인터를 이용해서 배열의 양 끝에서부터 안쪽으로 이동하면서 값이 일치하는지 확인한다. 만약 일치하지 않는 부분이 있다면 팰린드롬이 아니므로 false를 반환하고, 끝까지 일치한다면 팰린드롬이므로 true를 반환한다.

코드

function isPalindrome(head: ListNode | null): boolean {
  const arr: number[] = [];
  let ptr = head;
  while (ptr !== null) {
    arr.push(ptr.val);
    ptr = ptr.next;
  }

  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    if (arr[left] !== arr[right]) break;
    left++;
    right--;
  }
  return left >= right;
}

시간 / 공간 복잡도

  • 시간 복잡도: O(n) — 연결 리스트 순회 O(n) + 팰린드롬 확인 O(n)
  • 공간 복잡도: O(n) — 값 배열 저장