题解 | #判断一个链表是否为回文结构#

要验证回文结构，核心就是正序和倒序是否相同，那第一时间想到的就是拿第一个和最后一个比，循环比较。

所以思想最简单的实现流程：

1. 构建一个新链表，用来存倒序
2. 然后正序链表和倒序链表进行对比即可。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    ListNode* DescLink(ListNode* old_link){         //构建一个倒序链表
        ListNode *new_node, *new_head;
        new_head = NULL;
        while(old_link != NULL){
            new_node = (ListNode*)malloc(sizeof(old_link));
            new_node->val = old_link->val;
            new_node->next = new_head;
            new_head = new_node;
            old_link = old_link->next;
        }
        return new_head;
    }
    
    bool isPail(ListNode* head) {               //将正序链表和倒序链表循环比较元素即可
        // write code here
        ListNode *new_link = DescLink(head);
        while(head != NULL){
            if(head->val != new_link->val){
                return false;
            }
            head = head->next;
            new_link = new_link->next;
        }
        return true;
    }
};