LeetCode 234 Palindrome Linked List（回文連結清單）（*）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52661264

翻譯

給定一個單連結清單，判斷它是否是回文的。

跟進：

你可以隻用O(n)的時間和O(1)的空間嗎？

原文

Given a singly linked list, determine if it is a palindrome.

Follow up:

Could you do it in O(n) time and O(1) space?

分析

一種比較簡單的做法，用stack來存儲值，充分利用了棧的後進先出的特點進行對值的反轉。

public class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> original = new Stack<>();
        int len = 0;
        while (head != null) {
            original.push(head.val);
            head = head.next;
            len++;
        }
        Stack<Integer> compare = new Stack<>();
        for (int i = 0; i < len / 2; i++) {
            compare.push(original.pop());
        }
        if (len % 2 != 0)
            original.pop();
        while (!original.empty()) {
            int a = original.pop();
            int b = compare.pop();
            if (original.pop() != compare.pop())
                return false;
        }
        return true;
    }
}           

除此之外，也可以直接對連結清單進行反轉。

比如說對于 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1，反轉後半部分，得到 1 -> 2 -> 3 -> 4 -> 1 -> 2 -> 3，然後直接逐個周遊比較即可。下面的代碼中我已經附上了注釋，就不多說了。

代碼

Java

public class Solution {
    public ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode snake = head;
        int len = 0;
        // 計算長度，用時為O(n)
        while (snake != null) {
            len++;
            snake = snake.next;
        }
        snake = head;  // 為了下一步的重新周遊
        for (int i = 0; i < len / 2 - 1; i++) {
            snake = snake.next;
        }
        // 對于1-2-3-4-4-3-2-1，此時snake到第一個4
        // 對于1-2-3-2-1，此時snake到3
        // 将後半部分進行反轉，用時為O(n/2)
        snake.next = reverse(snake.next);
        ListNode snake2 = head;
        snake = snake.next;
        // 對未反轉的前半部分和經過反轉的後半部分進行逐個比較，用時為O(n/2)
        for (int i = 0; i < len / 2; i++) {
            if (snake2.val != snake.val) {
                return false;
            } else {
                snake = snake.next;
                snake2 = snake2.next;
            }
        }
        return true;
    }
}