【数据结构与算法】链表——回文链表

回文链表

LeetCode：回文链表

题目描述：

判断一个链表是否为回文链表。

示例：

输入: 1->2->2->1
输出: true

思想：

先用快慢指针取得中间位置的指针，将后半段链表进行翻转，再遍历比较前半段和后半段是否一致。时间复杂度O(3/2n)，空间复杂度O(1)

优化：在快慢指针的循环中，同时翻转前半段链表，随后从中间位置往两头遍历，时间复杂度O(n)

代码：

/**
 * 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||head.next==null)
            return true;
        ListNode mid=head,end=head;
        while(end!=null&&end.next!=null){
            mid = mid.next;
            end = end.next.next;
        }
        ListNode p=mid,q=mid.next,t;
        while(q!=null){
            t=q.next;
            q.next=p;
            p=q;q=t;
        }
        q=head;
        while(q!=mid){
            if(q.val!=p.val)
                return false;
            q=q.next;
            p=p.next;
        }
        return true;
    }
}

优化版，但是代码着实有点复杂，没有上一种方法直白

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)
            return true;
        ListNode mid=head,end=head.next,q=head.next,t;
        while(end!=null&&end.next!=null){
            end = end.next.next;
            t = q.next;
            q.next = mid;
            mid = q;q = t;
        }
        ListNode p=(end==null)?mid.next:mid;
        while(q!=null){
            if(q.val!=p.val)
                return false;
            q=q.next;
            p=p.next;
        }
        return true;
    }
}