leetCode - Reverse Linked List(LinkedList)

문제

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

 

Example 1:

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

Example 2:

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

 

---

배경지식

연결리스트 - 원소들을 저장할 때, 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조.

• 특징
  • k번째 원소를 확인/변경하기 위해 O(k(가 필요함
  • 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
  • 원소들이 메모리 상에 연속해 있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

 

문제해결

• slow, fast를 활용해서 주어진 head의 반을 가져오자
• reverse 할 수 있는 함수를 구현하자.
• reverse 된 list와 원래 list를 비교해서 틀린 값이 있으면 false로 리턴

*주의 할점: slow가 head를 참조하고 있다. reverse 함수를 통해 slow가 변경이 되기 때문에, head도 변경이 된다.

ex) head : [ 1, 2, 2, 1], slow: [2, 2, 1]  => head: [1,2], slow:[1,2,2] 

구현

let isPalindrome = function (head) {
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
    };
    
    let rev = reverse(slow);

    while (rev) {
        if (head.val !== rev.val) return false;
        head = head.next;
        rev = rev.next;
    }
    return true
}


function reverse(head) {
    let prev = null;
    let curr = head;
    let next = null;
    while (curr) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next
    }
    head = prev;
    return head;
}