【链表OJ题 6】链表的回文结构

系统管理员 2023-09-27 19:43 11阅读 0赞

**目录**

题目来源：

代码实现：

思路分析：

实现过程：

--------------------

## 题目来源： ##

[链表的回文结构\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com]

**题目描述：**

![60701e4ca7184694918d732970d9108b.png][]

**本题的难点在于时间复杂度为O(n)，空间复杂度为O(1)。**

## 代码实现： ##

struct ListNode* middleNode(struct ListNode* head)
    {
        struct ListNode* fast = head, * slow = head;
    
        while (fast && fast->next)
            {
                fast = fast->next->next;
                slow = slow->next;
            }
        return slow;
    }
    struct ListNode* reverse(struct ListNode* head)
    {
        struct ListNode* prev = NULL, * cur = head, * next = NULL;
    
        while (cur)
            {
                //尾插
                next = cur->next;
                cur->next = prev;
                prev = cur;
                //迭代
                cur = next;
            }
        return prev;
    }
    class PalindromeList {
    public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid = middleNode(A);
        struct ListNode* rmid = reverse(mid);
    
        while (rmid)
            {
                if (rmid->val != A->val)
                    return false;
                rmid = rmid->next;
                A = A->next;
            }
        return true;
    }
    };

## 思路分析： ##

因为回文结构是正着读反着读是一样的，因此我们找到链表的中间结点，然后从中间节点开始逆置到尾结点，然后用逆置后的链表与原链表的前半段对比，如果每个结点的 val 都相等，就说明此链表是回文结构。

![c5a8afbacff25d105d45fe6a621dcce9.png][]

### 实现过程： ###

1.使用快慢指针，初始化都指向原链表的头，慢指针一次走一步，快指针一次走两步，快指针走到空或快指针的 next 走到空时，慢指针指向的就是中间结点。

2.找到中间结点后，从中间结点开始到尾结点进行逆置。

这里讲的不够细致，找中间结点与逆置分别是两篇文章，里面讲的比较细致。

**找中间结点：**[http://t.csdn.cn/z3vm5][http_t.csdn.cn_z3vm5]

**逆置链表/反转链表：**[http://t.csdn.cn/Jt38p][http_t.csdn.cn_Jt38p]

我们分别将这两个功能封装成函数使用。

3.以逆置之后的链表头结点作为循环条件（这里其实不难发现逆置后的链表与原链表的长度相等），遍历整个逆置之后的链表，与原链表的 val 对比，如果存在哪个结点的val 不相等就返回 false，如果遍历完整个逆置后的链表都相等就返回 true。

**这样的解法可以实现题目的要求**：本题的难点在于时间复杂度为O(n)，空间复杂度为O(1)。

![6b1a987b9759a92608d5e0f49e38408c.png][]

![ae653c8911c1f646c5e1d401d243711a.png][]

如果大牛的您看到有什么问题留言给我，我一定会认真看的，谢谢您。如果您看了觉得有收获，关注 + 点赞支持一下呗。

\*\*\* 本篇结束 \*\*\*

[_nowcoder.com]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[60701e4ca7184694918d732970d9108b.png]: https://img-blog.csdnimg.cn/60701e4ca7184694918d732970d9108b.png
[c5a8afbacff25d105d45fe6a621dcce9.png]: https://img-blog.csdnimg.cn/img_convert/c5a8afbacff25d105d45fe6a621dcce9.png
[http_t.csdn.cn_z3vm5]: http://t.csdn.cn/z3vm5
[http_t.csdn.cn_Jt38p]: http://t.csdn.cn/Jt38p
[6b1a987b9759a92608d5e0f49e38408c.png]: https://img-blog.csdnimg.cn/img_convert/6b1a987b9759a92608d5e0f49e38408c.png
[ae653c8911c1f646c5e1d401d243711a.png]: https://img-blog.csdnimg.cn/img_convert/ae653c8911c1f646c5e1d401d243711a.png