【牛客网】链表的回文结构_链表回文结构o(n)

题目：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

题目分析：

解决这道题首先我们可以使用快慢指针找出中间节点，然后将中间节点开始后的链表进行逆置，再将中间节点前的链表和中间节点后的逆置过后的链表进行比较，当其中任意一个走到空的时候就停止。
步骤：
1、找中间节点
2、逆置
3、比较

代码实现：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    struct ListNode* FindMidNode(struct ListNode* phead)
    {
        struct ListNode* slow,*fast;
        slow = fast = phead;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    void  reverseList(struct ListNode** pphead)
    {
        struct ListNode* cur =* pphead;
        struct ListNode* newhead = NULL;
        while(cur)
        {
            struct ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        *pphead = newhead;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid = FindMidNode(A);
        //struct ListNode* rhead = reverList(mid);
        struct ListNode* rhead = mid;
        reverseList(&rhead);
        
        struct ListNode* head = A;
        while(rhead && head)
        {
            if(rhead->val != head->val)
            {
                return false;
            }
            rhead = rhead->next;
            head = head->next;
        }
         return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52