回文链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL) return true;
        int lenth = 0;
        ListNode *ln1, *ln2, *ln3;
        ln1 = ln2 = head;
        ln3 = NULL;
        //求出链表长度
        while(ln1)
        {
            lenth ++;
            ln1 = ln1->next;
        }
        cout << "lenth: " << lenth << endl;
        
        //将链表的前一半元素逆序
        for(int i = 0; i < lenth / 2; i++)
        {
            ln1 = ln2->next;
            ln2->next = ln3;
            ln3 = ln2;
            ln2 = ln1;
        }
        //如果长度为奇数
        //让ln2指向自己的next
        //也就是指向从中间元素的后一个元素开始的链表
        //ln3是从中间元素的前一个元素开始的逆序链表
        if(lenth % 2 == 1) ln2 = ln2->next;
        //开始比较ln2和ln3的每个元素知否相等，不相等则返回false
        for(int i = 0; i < lenth / 2; i++)
        {
            if(ln2->val != ln3->val)
                return false;
            else
                ln2 = ln2->next;ln3 = ln3->next;
        }
        
        return true;
    }
};