LEETCODE（力扣） 234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

自解

暴力新创了双向列表，把数组中每个元素用双向列表储存，然后双向列表进行回文判断
这个思路的一大原因是不想改变数组原有结构。
但运行结果只能用悲惨来形容

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) {
    int size=0,i=0;
    struct DuoList{
        int val;
        struct DuoList *last;
        struct DuoList *next;
    };
    struct DuoList head1;
    struct DuoList *p=&head1,*p1;
    head1.last==NULL;
    struct ListNode *temp=head;
    while(temp!=NULL)
    {
        struct DuoList *tempd=malloc(sizeof(struct DuoList));
        p->next=tempd;
        tempd->last=p;
        tempd->next=NULL;
        tempd->val=temp->val;
        p=p->next;
        temp=temp->next;
    }
    p1=head1.next;
    while(p1!=p&&p1->next!=p)
    {
        if(p1->val!=p->val)
        {
            return false;
        }
        p1=p1->next;
        p=p->last;
    }
    if(p1->next==p)
    {
        if(p1->val!=p->val)return false;
    }
    return true;
}

参考解：
将前半段链表反转，比较完回文再反转回去，也能不改变原链表结构，还不使用额外的空间

// 876. 链表的中间结点
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 206. 反转链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *pre = NULL, *cur = head;
    while (cur) {
        struct ListNode* nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

bool isPalindrome(struct ListNode* head) {
    struct ListNode* mid = middleNode(head);
    struct ListNode* head2 = reverseList(mid);
    while (head2) {
        if (head->val != head2->val) { // 不是回文链表
            return false;
        }
        head = head->next;
        head2 = head2->next;
    }
    return true;
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/palindrome-linked-list/solutions/2952645/o1-kong-jian-zuo-fa-xun-zhao-zhong-jian-rv0f3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

仿解

参考参考答案自己写一遍
刚开始尝试把中间数之前的链表反转，但实际上发现这样做面对奇数链表时，MID是中间那个数，无法做比较，如果做跳过中间数逻辑的话又要对链表成员的奇偶进行判断
那么连中间数一起反转呢？
考虑了一下，当数组成员只有两个时，中间数就是最后一个成员，反转前用Midtemp记录的未反转链表表头就成NULL了，还得额外增加判断逻辑。
于是换成了反转中间数以及中间数之后的链表，这样奇数的中间数在链表最后面，当前半部分未反转的链表遍历完成时，后半部分MID指针一定只想中间数或为NULL，单独对这部分进行判断就能得出结果

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *findMid(struct ListNode* head)//寻找链表中间节点
{
    struct ListNode *fast=head,*low=head;
    while(fast&&fast->next)
    {
        low=low->next;
        fast=fast->next->next;
    }
    
    return low;
}
struct ListNode * reverse(struct ListNode* head)//链表反转
{
    struct ListNode *next=head,*last=NULL;
    while(next!=NULL)
    {
        next=head->next;
        head->next=last;
        last=head;
        head=next;
    }
    return last;
}

bool isPalindrome(struct ListNode* head) {
    struct ListNode *Mid=findMid(head);//找中间数
    if(Mid==head)return true;//若中间数等于头节点，则链表只有一个成员，算为回文
    struct ListNode *Midtemp=Mid;//记录中间节点地址，用于判断比较结束的标志
    Mid=reverse(Mid);
    while(head!=Midtemp)//当头节点等于中间节点位置，代表遍历完毕
    {
        if(head->val!=Mid->val)return false;
        head=head->next;
        Mid=Mid->next;
    }
    if(Mid!=NULL)//若此时反转部分链表为遍历完全
    {
        if(Mid->next==NULL)return true;//若只剩一个中间数则为回文
        else return false;
    }
    Mid=reverse(Mid);//恢复链表
    return true;
}