leetcode鍊表之回文鍊表

序

本文主要記錄一下leetcode鍊表之回文鍊表

題目

請判斷一個鍊表是否為回文鍊表。

示例 1:

輸入: 1->2
輸出: false

示例 2:

輸入: 1->2->2->1
輸出: true

進階：
你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題？

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/palindrome-linked-list
著作權歸領扣網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
題解
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        Stack stack = new Stack();
        ListNode cursor = head;
        while(cursor != null) {
            stack.push(cursor.val);
            cursor = cursor.next;
        }

        cursor = head;
        while(cursor != null) {
            int val = (int)stack.pop();
            if (val != cursor.val) {
                return false;
            }
            cursor = cursor.next;
        }
        return true;
    }
}
小結
這裡使用Stack來解決，先遍歷一遍放到Stack中，之後再次遍歷，挨個跟stack.pop出來的比較
doc