Leetcode-234 回文链表

题目转载自Leetcode
请判断一个链表是否为回文链表。

示例 1:

示例 2:

题解

方法一：反转后半部分链表

题解参考自数据结构和算法

反转后半部分链表，将反转后的链表和前半部分链表比较

1.找到链表中点：

快慢指针：fast走两步，slow走一步–>slow为中点

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

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

2.判断链表是奇数长度还是偶数长度

如果fast不为空(1+2+2+…+2不为空)–>说明链表的长度是奇数个–>找的是slow.next
否则，找的是slow

3.反转以中点（slow或者slow.next）开始的链表(pre,cur,tmp)

反转循环终止的条件是cur!=null，返回值是pre
1）记录当前节点的下一个节点
cur.next=tmp
2)cur的下一个节点指向pre
cur.next=pre
3）pre和cur都向前移动
pre=cur
cur=tmp

4.使得fast重新指向head，开始遍历比较fast.val和slow.val

class Solution {
    public boolean isPalindrome(ListNode head) {
        //找到链表中点
        ListNode fast=head,slow=head;
        //这块是为了避免执行fast.next.next报错
        while(fast!=null && fast.next != null){
            fast=fast.next.next;
            slow=slow.next;
        }
        if(fast!=null) slow=slow.next;

        slow=reverse(slow);
        fast=head;
        while(slow!=null){
            if(slow.val!=fast.val) return false;
            slow=slow.next;
            fast=fast.next;
        }
        return true;

    }

    private ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        ListNode tmp;
        //这块的终止条件是cur不为null
        while(cur!=null){
            tmp=cur.next;
            cur.next=pre;
            
            pre=cur;
            cur=tmp;
        }
        //循环结束时cur=null，所以此处返回pre
        return pre;
    }
}

方法二：将值复制到数组中后用双指针法

算法
一共为两个步骤：

复制链表值到数组列表中。
使用双指针法判断是否为回文。

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}

方法三、使用栈解决

我们知道栈是先进后出的一种数据结构，这里还可以使用栈先把链表的节点全部存放到栈中，然后再一个个出栈，这样就相当于链表从后往前访问了，我们只需要拿链表的后半部分和前半部分比较即可，没必要全部比较，所以这里可以优化一下。

public boolean isPalindrome(ListNode head) {
    if (head == null)
        return true;
    ListNode temp = head;
    Stack<Integer> stack = new Stack();
    //链表的长度
    int len = 0;
    //把链表节点的值存放到栈中
    while (temp != null) {
        stack.push(temp.val);
        temp = temp.next;
        len++;
    }
    //len长度除以2
    len >>= 1;
    //然后再出栈
    while (len-- >= 0) {
        if (head.val != stack.pop())
            return false;
        head = head.next;
    }
    return true;
}