leetcode_【234】回文链表

1.题目描述

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

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

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

2.解题思路

方法1：将链表的数值依次入栈，然后弹栈跟listnode从头到尾比较

方法2：快慢指针弦找到中间点，再反转后面链表，再遍历比较

3.代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
            Stack<Integer> stack = new Stack<>();
            ListNode res = head;
            //链表入栈
            while (head!=null){
                stack.push(head.val);
                head = head.next;
            }
            //弹出比较
            while (res!=null){
                if(stack.pop() == res.val){
                    res = res.next;
                }else {
                    return false;
                }
            }
        return true;
        }
}

方法2：

/**
 * 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 || head.next == null) return true;
        ListNode lat = head.next;
        ListNode pre = head;
        //快慢指针,pre一次一步，lat一次两步
        while(lat != null && lat.next != null){
            lat = lat.next.next;
            pre = pre.next;
        }
        //转置后半链表
        ListNode cur = pre.next;
        pre.next = null;
        ListNode p = null;
        while (cur != null){
            ListNode q = cur.next;
            cur.next = p;
            p = cur;
            cur = q;
        }
        //遍历比较
        while(p != null && head != null){
            if(p.val != head.val){
                return false;
            }
            p = p.next;
            head = head.next;
        }
        return true;
    }
}

4.提交记录