234. 回文链表

题目来源

leetcode

题目描述

题目解析

使用栈

先按顺序把所有的结点值都存入到一个栈 stack 里，然后利用栈的后入先出的特性，就可以按顺序从末尾取出结点值了，此时再从头遍历一遍链表，就可以比较回文的对应位置了，若不同直接返回 false 即可，参见代码如下：

/**
 * 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<Integer >stack = new Stack<>();
        ListNode temp = head;
        while (temp != null){
            stack.push(temp.val);
            temp = temp.next;
        }

        temp = head;
        while (temp != null){
            if (temp.val != stack.pop()){
                return false;
            }
            temp = temp.next;
        }

        return true;
    }
}

反转整个链表比较

class Solution {
    //  不能异或相消，也不能set，因为回文顺序很重要
    public boolean isPalindrome(ListNode head) {
         if (head == null){
            return true;
        }
        
        // 反转这个链表，然后和原来的链表相比较，如果相同，则表示是回文的
        ListNode dummy = null;
        ListNode temp = head;  //  因为head以后还需要用，所以不能破坏原来的链表结构
        while (temp != null){
            ListNode node = new ListNode(temp.val);
            node.next = dummy;
            dummy = node;
            temp = temp.next;
        }
        
        while (dummy != null){
            if (dummy.val != head.val){
                return false;
            }
            
            dummy = dummy.next;
            head = head.next;
        }
        
        return true;
    }
}

反转半个链表

用快慢指针遍历的同时翻转前半部分，然后与后半部分比较即可。

注意，如果是奇数个链表，最放弃中间的那个节点

class Solution {
    public boolean isPalindrome(ListNode head) {
                if (head == null){
            return true;
        }


        ListNode fast = head,  slow = head; // 快慢指针
        // 找中间节点的同时翻转前半部分
        ListNode pre = null, p = null; // head不为空
        while (fast != null && fast.next != null){
            p = slow;

            slow = slow.next;
            fast = fast.next.next;

            p.next = pre;
            pre = p;
        }

        if (fast != null){  // 奇数个节点
            slow = slow.next; // 放弃中间节点
        }

        while (p != null){
            if (slow.val != p.val){
                return false;
            }

            slow = slow.next;
            p = p.next;
        }

        return true;
    }
}