【每日算法Day 93】回文链表

LeetCode 234. 回文链表 (opens new window)

题目描述

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

示例

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

输入: 1->2
输出: false

解题思路

由于一般的单向链表不能逆序遍历节点，所以可以使用栈来保存第一次访问过的节点，再出栈作比较。

public boolean isPalindrome(ListNode head) {
    Deque<ListNode> stack = new LinkedList<>();
    ListNode first = head;
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    while (first != null) {
        ListNode last = stack.pop();
        if (first.val != last.val) return false;
        if(first == last) break;
        first = first.next;
    }
    return true;
}

或者使用递归，本质上也是使用了栈，都需要O(n)的额外空间。

class Solution {
    private ListNode left = null;

    public boolean isPalindrome(ListNode head){
        left = head;
        return check(head);
    }

    private boolean check(ListNode head){
        if(head == null) return true;
        boolean b = check(head.next) && left.val == head.val;
        left = left.next;
        return b;
    }
}

为了避免使用O(n)的额外空间，我们可以使用双指针法得到链表的后半部分的开始节点，并在继续遍历时反转后半部分。这样就能对后半部分和前半部分进行遍历比较了。

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //如果fast不为空则说明有奇数个节点，后半部分的开始在slow.next
        if (fast != null) slow = slow.next;
        ListNode end = reverse(slow);
        while (end != null) {
            if (end.val != head.val) return false;
            end = end.next;
            head = head.next;
        }
        return true;
    }

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