LeetCode234 回文链表

题目链接：LeetCode

描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例

输入：head = [1,2,2,1]
输出：true

输入：head = [1,2]
输出：false

方法一

思路

首先找到链表的中间结点 mid：

• 如果链表有奇数个节点，那么找的是正中间的节点。

• 如果链表有偶数个节点，那么找的是正中间右边的节点。

然后反转从 mid 到链表末尾的这段，其头节点记作 head2。

最后，同时遍历 head 和 head2

代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = findMid(head);
        ListNode head2 = reverse(mid);
        while(head2 != null){
            if(head.val != head2.val){
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }

    public ListNode findMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast!= null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while(cur!=null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

方法二

思路

使用栈和队列来存储列表，然后遍历比较

代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<ListNode> deque = new LinkedList<>();
        Queue<ListNode> queue = new LinkedList<>();
        ListNode cur = head;
        while(cur != null){
            deque.offerFirst(cur);
            queue.offer(cur);
            cur = cur.next;
        }
        while(!deque.isEmpty()){
            ListNode node1 = deque.pollFirst();
            ListNode node2 = queue.poll();
            if(node1.val != node2.val){
                return false;
            }
        }
        return true;
    }
}