链表的回文结构

链表的回文结构

什么是回文结构 ：
1，2，3，4，5
1，2，3，3，2，1
像这样正着念和反着念都是一样的的结构就是回文结构

判断链表是否是回文结构：
思路：
第一步：先找到链表的中间节点
第二步：讲中间节点之后的节点进行反转
第三步：让两个引用一个从前往后走，一个从后往前走，当它们的data不相等的时候就直接返回false。当链表长度是奇数的时候，它们相遇的时候就停止。当链表长度是偶数的时候，前面一个引用此时指向的是后面这个引用。直接返回true。

代码示例：

public boolean Huiwen() {//判断链表是否是回文结构
        //第一步：寻找中间节点
        Nodee fast = this.head;//定义一个快指针一个慢指针先来寻找中间节点
        Nodee slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }//这个循环结束的时候slow就是在中间节点，偶数长度的话就是在中间两个节点的第二个
        //第二步：反转中间节点后面的节点
        Nodee cur = slow.next;//此时的slow处于中间节点。
        while (cur != null) {//循环结束条件就是cur把最后一个节点也反转完的时候
            Nodee del = cur.next;//让del来控制cur往后走
            cur.next = slow;//让cur.next指向前面的节点。实现反转
            slow = cur;//让slow也跟着往后走。顺序如果和下面相反的话，slow就走不了了，也就不能让cur实现反转了。
            cur = del;//让cur往后走。
        }//这个循环结束的时候slow处于最后一个节点处。且已经反转完成
        //第三步，判断head.data是否和slow.data相等，如果相等的话，两个都继续相对走。
        while (this.head != slow) {//这个循环结束条件是head和slow相遇的时候。相遇的时候它们两个所有的data才判断完
            if (head.data != slow.data) {//这里是当它们两个的data中有一个不相等的时候，就代表不是回文链表，直接返回false
                return false;
            }
            if (this.head.next == slow) {//这里是当链表长度是偶数的时候，head和slow能走到这里来，说明此时它们的data还是相等的，但是此时head指向的是slow，slow又指回去了。
                return true;
            }
            slow = slow.next;//奇数的时候就直接让slow和head走到它们相遇为止。
            head = head.next;
        }
        return true;//上面那个循环能走完，说明slow能和head相遇，说明它们之间的所有data都相等，直接返回true

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

总结：
1.找中间节点：

定义一个快指针fast，一个慢指针slow。让fast走两步，让慢指针走一步，当fast为null或者fast.next为null的时候结束。此时slow对应的刚好就是中间节点或者中间两个节点的第二个。

二.反转：

定义一个cur=slow.next,当cur不为null的时候，定义一个del=cur.next。然后让cur.next = slow,再让cur=del，再让slow = cur。直到cur = null，后半链表也就反转完成。

三.进行判断：

首先判断head.data是否等于slow.data，如果不相等，直接返回false;如果相等，head = head.next,slow = slow.next，当是奇数长度的时候，slow=head就是终止条件，当是偶数长度的时候，此时的slow已经走到了反面的最后一个节点。判断head.next 是否等于slow，如果相等直接返回true。

特殊情况：单链表里面为空的时候，直接返回false。