13 팰린드롬 연결 리스트

연결 리스트가 팰린드롬 구조인지 판별하라

My solution

leetCode는 입력으로 링크드리스트의 head만 넘겨주는 방식으로 입력을 준다.

jest로 테스트를 돌리면서 문제를 풀고 있어서 이 형식에 맞는 입력을 만들기 위해서 아래처럼 세팅했다. 이후linkedList.js 파일을 만들어 정의와 프로토타입 메서드는 분리해뒀다.

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

function LinkedList() {
  this.head = null;
  this.length = 0;
}

LinkedList.prototype.size = function () {
  return this.length;
};

LinkedList.prototype.isEmpty = function () {
  return this.length === 0;
};

LinkedList.prototype.printNode = function () {
  let out = '';
  for (let node = this.head; node != null; node = node.next) {
    out += `${node.val} -> `;
  }
  console.log(`${out} null`);
};

LinkedList.prototype.append = function (value) {
  const node = new ListNode(value);
  let current = this.head;

  if (this.head === null) {
    this.head = node;
  } else {
    while (current.next != null) {
      current = current.next;
    }
    current.next = node;
  }

  this.length++;
};
// TC1
const ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(2);
ll.append(1);
// TC2
const ll2 = new LinkedList();
ll2.append(1);
ll2.append(2);

test('TC1', () => {
  expect(palindromeLinkedList(ll.head)).toStrictEqual(true);
});
test('TC2', () => {
  expect(palindromeLinkedList(ll2.head)).toStrictEqual(false);
});
JavaScript
복사

Code

const palindromeLinkedList = function (head) {
  let prev = null;
  let tHead = head;
  const arr = [];
  // tHead를 바꾸면서 배열화
  while (tHead) {
    arr.push(tHead.val);
    // 현재 tHead.next로 노드 거꾸로 연결하고 prev는 tHead를 저장하면 tHead를 다음 노드로 변경
    [tHead.next, prev, tHead] = [prev, tHead, tHead.next];
  }
  // 정방향 배열과 역방향 연결 리스트를 비교
  return arr.every(value => {
    // 맨 뒤 노드를 가지고 있는 prev를 이용해서 값을 비교
    const i = prev.val === value ? 1 : 0;
    prev = prev.next;
    return i;
  });
};
JavaScript
복사

Solution

1. 리스트 변환

파이썬의 리스트는 pop에 인덱스를 줄 수 있다. 연결리스트를 리스트로 변환한다.

pop(0)을 하기 때문에 모든 값이 한 칸씩 시프팅되어 시간복잡도 O(n)이 발생한다.

2. 데크를 이용한 최적화

데크는 양방향 모두 O(1)에 가능하다.

이 방식이 가독성은 훨씬 좋은데 속도가 매우 느리게 나온다. js에서는 데크를 따로 구현해야해서 배열로 했는데 시프팅이 있기 때문으로 보인다. 데크를 구현한다음 q를 수정해 적용해볼 수 있을듯 하다.

const palindromeLinkedList = function (head) {
  if (head === null) return true;
  const q = [];
  let node = head;
  while (node !== null) {
    q.push(node.val);
    node = node.next;
  }
  while (q.length > 1) {
    if (q.shift() !== q.pop()) return false;
  }
  return true;
};
JavaScript
복사

3. Go로 데크 구현

데크 자료형을 지원하지 않아 100줄 이상의 코드 구현이 필요해진다.

4. 런너를 이용한 우아한 풀이

제대로 된 풀이법이다.

속도도 약간 더 빨랐다.

const palindromeLinkedList = function (head) {
  let rev = null;
  let slow = head;
  let fast = head;
  // fast가 끝에 도달하면 slow는 가운데 노드
  while (fast && fast.next) {
    fast = fast.next.next;
    [rev, rev.next, slow] = [slow, rev, slow.next];
  }
  // 입력이 홀수개면 slow가 한 칸 더 이동해야 중앙을 넘긴다.
  if (fast) slow = slow.next;
  // 이후 slow가 가리키는 곳부터 만들어둔 rev(역순 연결리스트)를 차례대로 비교해나간다.
  // rev 초기값이 null이었으므로 팰린드롬일 때 마지막 rev.next는 null이 되어 최종 rev는 null이다.
  while (rev && rev.val === slow.val) {
    [slow, rev] = [slow.next, rev.next];
  }
  return !rev;
};
JavaScript
복사