[数据结构与算法]【链表OJ】牛客 - OR36 链表的回文结构（ 2016校招真题）

题目链接

思路一

此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。

所以可以简化为三个问题：

• 找到中间结点 （指路这篇博客链表的中间结点）
• 后半段链表逆序 （指路这篇博客 反转链表 ）
• 逐一比对

图文分析

偶数个结点

奇数个结点

代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // 找到中间结点
        // 后半段链表逆序
        // 逐个进行比较
        ListNode* midnode = midNode(A);
        ListNode* p2 = reverseSList(midnode);
        ListNode* p1 = A;
        
        while(p1 && p2)
        {
            if(p1->val != p2->val)
                return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
    
private:
    // 返回中间结点
    // 快慢指针
    ListNode* midNode(ListNode* A)
    {
        ListNode* fast, *slow;
        fast = slow = A;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    
    // 后半段链表逆序 返回逆置后头结点
    // 构造不带哨兵位的新的链表
    ListNode* reverseSList(ListNode* A)
    {
        if(A == NULL || A->next == NULL) {
            return A;
        }
        
        ListNode* newhead = NULL, *cur = A;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        
        return newhead;
    }
    
};

思路二

其实本题对整条链表进行逆置，之后再逐一比对也是可以的嗷~

博主这么勤快，当然会来展示啦！ 关注三连疯狂暗示(#^.#)

图文分析

true的情况

false的情况

代码

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // 链表逆序
        // 逐个进行比较
        ListNode* p2 = reverseSList(A);
        ListNode* p1 = A;
        
        while(p1 && p2)
        {
            if(p1->val != p2->val)
                return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
    
private:
    // 链表逆序 返回逆置后头结点
    // 构造不带哨兵位的新的链表
    ListNode* reverseSList(ListNode* A)
    {
        if(A == NULL || A->next == NULL) {
            return A;
        }
        
        ListNode* newhead = NULL, *cur = A;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        
        return newhead;
    }
    
};