説明

値が整数である単一連結リスト node が与えられた場合、連結リストが回文を形成するかどうかを判断します.

制約:

n ≤ 100,000 n は node の長さです

例1

入力

node = [5, 3, 5]

出力

true

説明

5 -> 3 -> 5 is a palindrome.

例2

入力

node = [12, 8, 12]

出力

true

説明

The values of the linked list are the same forwards and backwards.

直感

高速ポインターと低速ポインターを使用して mid を検索します.

右ハーフリンクを逆にする

左右比較

実装

import java.util.*;

/**
 * class LLNode {
 *   int val;
 *   LLNode next;
 * }
 */
class Solution {
    public boolean solve(LLNode node) {
        LLNode slow = node, fast = node;
        while (slow != null && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // fast rest to head;
        LLNode left = node;
        LLNode right = reverse(slow);
        while (left != null && right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    private LLNode reverse(LLNode slow) {
        LLNode pre = null, curr = slow, next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}

時間の複雑さ

時間: O(n)

スペース: O(1)

直感

indexMap の使用: HashMap<Integer, LinkedList<Integer>> map

店舗番号のインデックス.

と index を length - 1 - index と比較します

実装

import java.util.*;

/**
 * class LLNode {
 *   int val;
 *   LLNode next;
 * }
 */
class Solution {
    public boolean solve(LLNode node) {
        HashMap<Integer, LinkedList<Integer>> map = new HashMap<>();
        int index = 0;
        while (node != null) {
            LinkedList<Integer> indexes = map.getOrDefault(node.val, new LinkedList<>());
            indexes.add(index);
            map.put(node.val, indexes);
            index++;
            node = node.next;
        }

        int length = index;
        for (LinkedList<Integer> indexes : map.values()) {
            for (int i : indexes) {
                if (!indexes.contains(length - 1 - i)) {
                    return false;
                }
            }
        }

        return true;
    }
}

時間の複雑さ

時間: O(N)

スペース: O(N)