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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 *

//思路：首先将原来的链表的所有节点从头到尾，头插到新链表中
//随后让新链表和原链表从头到尾一一遍历，遍历的同时比较两者节点的数据是否相同
//若不相同则返回false，若遍历完了没有不相同的也就是全部相同则返回true
//通俗点说就是将该链表元素都逆置到一个新链表然后逆置的和顺着的比较若相同时回文结构
//若不同则不是回文结构。



typedef int DataType;
//开辟空间
struct ListNode* SLTSpace(DataType x)
{
	//开辟空间
	struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (p == NULL)
	{
		perror("Space malloc fail");
		return NULL;
	}
	p->val = x;
	p->next = NULL;
	return p;
}

//头插
void SLPushFront(struct ListNode** pphead, DataType x)
{
	//创建节点
	struct ListNode* newNode = SLTSpace(x);

	//无节点的情况下直接插入
	if (*pphead == NULL)
	{
		*pphead = newNode;
		return;
	}
	//节点存在的情况下插入
	newNode->next = *pphead;
	*pphead = newNode;
 
}

bool isPail(struct ListNode* head ) {
    // write code here

    //链表为空的情况直接返回falsn e
    if(head==NULL) return false;

    //若链表中仅有一个节点的情况是回文结构
    if(head->next==NULL) return true;

    //若链表中有两个或多个节点的情况下需要进行比较

    //创建一个新链表将原本链表中的元素尾插到新链表中
    struct ListNode* phead=NULL;

    //遍历原先链表进行头插
    struct ListNode* cur=head;
    while(cur)
    {
        //头插
        SLPushFront(&phead,cur->val);
        cur=cur->next;
    }

    //随后将两个链表进行对比
    struct ListNode* cur1=head;
    struct ListNode* cur2=phead;
    while(cur1 && cur2)
    {
        if(cur1->val!=cur2->val)
        {
            return false;
        }
        cur1=cur1->next;
        cur2=cur2->next;
    }
     return true;
}