链表回文判断(基于链表反转)—Java实现

学习数据结构的时候遇到一个经典的回文链表问题

• 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

---

如果有链表反转的基础，实现链表回文判断就简单的多，如果对反转链表不熟悉，可以参考这篇。

思路很简单，先找到链表的中间Node，采用的快慢指针法。

• 慢指针一次走一步，快指针一次走两步，当快指针触底的时候，慢指针到达了重点，如果链表总数是偶数，则慢指针停在相对左边的Node上。
• 找到中点后，对中点后面的链表进行反转。
• 从头尾开始向中间移步，每次比较是否相同。

---

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    //第一步找到中点
    //从中点开始将后续结点反转
    //两遍开始next比较直到相遇
    public boolean chkPalindrome(ListNode A) {
        ListNode node1 = A;
        ListNode node2 = A;
        while(node2.next!=null&&node2.next.next!=null){
            node1=node1.next;
            node2=node2.next.next;
        }
        ListNode head2 = node1.next;
        //反转链表过程,推荐采用遍历法
        ListNode temp = null;
        ListNode pre = null;
        while(head2!=null){
            temp = head2.next;
            head2.next = pre;
            pre = head2;
            head2=temp;
        }
        //对比过程
        ListNode n1 = A;
        ListNode n2 = pre; //最后一个节点
        while(n1.next!=null){
            if(n1.val!=n2.val){
                return false;
            }
            n1=n1.next;
            n2=n2.next;
        }
        return true;
    }
}