LeetCode 234 - Palindrome Linked List (Easy)

문제

LeetCode - 234번

풀이 과정

주어진 링크드리스트가 팰린드롬 인지 판단하는 문제입니다.

시간 복잡도가 O(N) 이면서 공간 복잡도가 O(1) 으로 구현하기 위해서 재귀 함수를 사용했습니다.
이를 위해 먼저 링크드 리스트의 길이를 구한 다음, 중앙 위치까지 이동해서 팰린드롬 유무를 판단합니다.
이는 a[i] ~ a[j] 까지의 링크드 리스트가 팰린드롬이기 위해서는
a[i+1] ~ a[j-1] 까지가 팰린드롬이고 a[i] == a[j] 이기 때문입니다.

그러므로 각각의 재귀 호출 과정에서 반환값으로 팰린드롬 유무 와 tail 노드 를 반환해서
재귀 호출 과정에서 각각의 서브 리스트의 양 끝 노드를 비교해줍니다.

코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  const len = getLength(head);
  let half = len % 2 ? Math.floor(len / 2) : Math.floor(len / 2) - 1;

  if (len === 0) return true;

  const [answer] = dfs(len % 2 === 0, half, head, 0);
  return answer;
};

function dfs(even, pivot, head, depth) {
  if (depth === pivot) {
    if (even) return [head.val === head.next.val, head.next.next];
    else return [true, head.next];
  }

  const [subCheck, tail] = dfs(even, pivot, head.next, depth + 1);
  return [subCheck && head.val === tail.val, tail?.next];
}

function getLength(head) {
  if (!head) return 0;
  return getLength(head.next) + 1;
}