程序员代码面试指南 2.7：判断一个链表是否为回文结构

解法一：栈

1、思路

遍历链表放入栈中，弹出栈元素的同时从头遍历链表，比较栈顶元素与链表当前元素是否相等即可；
时间复杂度 $O(N)$ ，空间复杂度 $O(N)$ 。

2、代码

list_node * check(list_node * head)
{
    if (head == nullptr || head->next == nullptr)
    {
        cout << "true" << endl;
        return head;
    }

    stack<int> stk;         //栈中只需要存链表节点的值即可，不用存下整个节点，节约空间
    auto p = head;
    while (p != nullptr)
    {
        stk.push(p->val);       //链表进栈
        p = p->next;
    }

    p = head;
    while (!stk.empty())
    {
        auto tmp = stk.top();   //链表出栈
        if (tmp != p->val)
        {
            cout << "false" << endl;
            return head;
        }

        stk.pop();
        p = p->next;
    }

    cout << "true" << endl;
    return head;
}

解法二

1、思路

用双指针遍历找到单链表中间节点；
反转后半部分单链表；
从头遍历两条单链表，对比其值是否相等；
时间复杂度 $O(N)$ ，空间复杂度 $O(1)$ 。

2、代码

list_node* findMid(list_node* head)         //单链表找中点
{
    auto fast = head, slow = head;
    while (fast->next != nullptr && fast->next->next != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;
}

list_node* reverseList(list_node* head)     //反转单链表
{
    auto pre = head, cur = head->next;
    while (cur)
    {
        auto ne = cur->next;
        cur->next = pre;
        pre = cur, cur = ne;
    }

    head->next = nullptr;
    return pre;
}

bool isSame(list_node* L1, list_node* L2)   //判断两条单链表是否相等
{
    auto p1 = L1, p2 = L2;
    while (p2 != nullptr)
    {
        if (p1->val != p2->val)
        {
            return false;
        }

        p1 = p1->next, p2 = p2->next;
    }

    return true;
}

list_node * check(list_node * head)
{
    if (head == nullptr || head->next == nullptr)
    {
        cout << "true" << endl;
        return head;
    }

    list_node* mid = findMid(head);
    list_node* L1 = head, *L2 = mid->next;  //将链表从中一分为二

    L2 = reverseList(L2);

    if (isSame(L1, L2) == true)
    {
        cout << "true" << endl;
        return head;
    }
    else
    {
        cout << "false" << endl;
        return head;
    }
}