Leetcode #234 - 회문 연결 목록

문제: 단일 연결 목록이 주어지면 그것이 회문인지 확인하십시오.

방법 1: 값 배열 만들기

연결 목록의 구조는 목록의 전체 크기에 대한 액세스를 제공하지 않습니다. 이 문제를 해결하기 위해 목록을 반복하고 노드 값을 배열에 푸시할 수 있습니다. 이 시점에서 우리는 배열의 길이에 접근할 수 있고 단일 포인터i를 사용하여 배열에서 서로 반대되는 값을 비교할 수 있습니다.

var isPalindrome = function(head) {
    let values = []
    // push all node values into an array
    while (head !== null) {
        values.push(head.val)
        head = head.next
    }
    // iterate over array and compare values
    for (let i = 0; i < values.length >> 1; i++) {
        // (values.length - i - 1) is our virtual pointer
        if (values[i] !== values[values.length - i - 1]) return false
    }
    return true
};

이 방법의 시간 및 공간 복잡도는 O(n)

방법 2: 제자리에서 후반 반전

fast 및 slow 포인터를 사용하여 각각 목록의 중앙과 끝으로 이동할 수 있습니다. 중심을 결정할 수 있게 되면 slow 포인터를 사용하여 목록의 후반부를 역으로 다시 연결합니다. 나는 이 방법을 뱀을 잡고 꼬리를 머리로 바꾸는 것으로 개념화하고, 그 결과 가운데에 꼬리가 있는 머리가 둘 달린 뱀(ListNode.next = null )이 생깁니다.

var isPalindrome = function(head) {
    if (head === null || head.next == null) return true
    let slow = head
    let fast = head

    while (fast !== null && fast.next !== null) {
        fast = fast.next.next
        slow = slow.next
    }
    // if list length is odd, move slow over one to start
    // the second half of the list
    if (fast) {
        slow = slow.next
    }

    // reverse the second half of the list
    slow = reverse(slow)
    fast = head

    // check for palindromicity
    while (slow) {
        if (slow.val !== fast.val) {
            return false
        }
        slow = slow.next
        fast = fast.next
    }
    return true
}

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

추가 배열을 생성하지 않기 때문에 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)입니다.