234. 回文链表


回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用  O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
解析:见 org 第三种解法
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // org 时间空间复杂度都是 O(n)
    // equals [-129,-129]
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> res    = new ArrayList<Integer>();
        ListNode cur = head;
        while(cur != null)&#123;
            res.add(cur.val);
            cur = cur.next;
        &#125;
        int front=0;
        int tail =res.size()-1;
        while(front<=tail)&#123;
            if(!res.get(front).equals(res.get(tail)))&#123;
                return false;
            &#125;
            front++;
            tail--;
        &#125;
        return true;
    &#125;

    // //第一次 提交 针对奇数个元素 不成立。
    // public boolean isPalindrome(ListNode head) &#123;
    //     if(head==null)&#123;
    //         return false;
    //     &#125;
    //     Stack<Integer> res    = new Stack<Integer>();
    //     ListNode cur = head;
    //     while(cur!=null)&#123;
    //         if(!res.isEmpty()&&res.peek() == cur.val)&#123;
    //             res.pop();
    //         &#125;
    //         else&#123;
    //             res.add(cur.val);
    //         &#125;
    //         cur = cur.next;
    //     &#125;
    //     return res.isEmpty();
    // &#125;
&#125;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
二叉树的最大深度 二叉树的最大深度
二叉树的最大深度给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:  叶子节点是指没有子节点的节点。示例:给定二叉树 [3,9,20,null,null,15,7], **  3****   /
2020-09-11 future
下一篇 
206. 反转链表 206. 反转链表
反转一个单链表。 示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
2020-09-11 future
  目录