题解 | #链表的回文结构#

回文结构, 即该链表从头往后和从后往前遍历都是一样的结果, 因为该题中, 链表是单链表, 所以不能直接从左往右和从右往左同时遍历, 因此, 我们需要把链表一分为二, 后面的部分需要进行逆序, 然后再对两个部分进行同时遍历, 然后就能确定是否是回文结构了

先要找到链表的中间位置, 可以通过快慢指针的方法解决, 快指针一次走两步, 慢指针一次走一步, 如此最后快指针停止时, 慢指针指向的位置就是链表的中间节点, 然后进行逆序操作, 逆序操作采用递归算法, 将需要逆序部分的头节点传入, 递归的出口为到达链表最后的节点, 然后就将头节点设置为这个节点, 然后返回这个节点作为尾节点, 每次递归出一层之后, 就将当前层的节点加到这个节点的末尾, 全部出去之后, 要将最后一个节点的next域设置为空, 否则会出现循环的情况

然后就从头节点和逆序部分头节点同时开始遍历, 两边的长度是保证相等的, 中间的那个节点不会被比较(奇数个数时), 那么循环的设置条件可以设置为左边的指针不等于原来的中间节点(也就是逆序链表的最后一个位置)

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {

    public ListNode reverse(ListNode head,ListNode[] newHead) {
        if(head.next == null) {
            newHead[0] = head;
            return head;
        }
        ListNode tail = reverse(head.next,newHead);
        tail.next = head;
        head.next = null;
        return head;
    }

    public boolean chkPalindrome(ListNode A) {
        // write code here
        ListNode[] newHead = {
            new ListNode(0)
        };
        ListNode slow = A;
        ListNode fast = A;
        while(fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tail = reverse(slow,newHead);
        tail.next = null;
        ListNode cur1 = newHead[0];
        ListNode cur2 = A;
        while(cur2!=slow && cur1!=null) {
            if(cur1.val!=cur2.val) {
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }
}