【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）_Java

正如标题所说，本文会图文详细解析三道单链表oj题，分别为：

反转链表 （简单）
链表的中间节点 （简单）
链表的回文结构 （较难）

把他们放在一起讲的原因是： 反转链表 和 链表的中间节点 是 链表的回文结构 的基础

为什么这样说？请往下看：

1. 反转链表

💭做题思路

遍历链表，改变每个节点的链接方向，使其链向前节点
如果是第一个节点，使其链向 null

这里需要3个指针：

cur 指向当前需要修改的节点
prev 记录 cur 的前一个节点， cur 要链向此节点
next 记录 cur 的后一个节点，避免 cur 改变链接方向后找不到下个节点

🎨画图理解

✍️代码实现

struct listnode* reverselist(struct listnode* head)
{
    struct listnode* cur = head;
    struct listnode* prev = null;
    while (cur != null)
    {
        struct listnode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

最后提交代码试试：

完美通过，本题并不难，来搞下一题

2. 链表的中间节点

💭做题思路

快慢指针
搞两个指针，一个叫 fast ，一个叫 slow
快指针 fast 一次走两步
慢指针 slow 一次走一步
当 fast 走到 null 时， slow 恰好在中间，此时 slow 指向的节点就是中间节点

🎨画图理解

✍️代码实现

struct listnode* middlenode(struct listnode* head)
{
    struct listnode* slow = head;
    struct listnode* fast = head;
    while (fast != null && fast->next != null)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

提交代码：

这道题也很简单，主要就是快慢指针的思路，第一次接触的话可能想不到这种方法

接下来就是本文重点了，前面这些只是开胃小菜

3. 链表的回文结构

💭做题思路

1. 找到中间节点

2. 反转中间节点及其之后的链表

3. 此时把链表分为两段：

未反转的链表为一段，用指针 list1 指向这段链表的头节点
反转过的链表为另一段，用指针 list2 指向这段链表的头节点

4. 比较 list1 和 list2 节点的值是否相等

如果相等， list1 和 list2 同时往后走，去比较下一组数据
如果不相等，说明链表不是回文结构，返回 false

5. 当 list2 走到 null 处时，说明此链表是回文结构，返回 true

🎨画图理解

可以看到本题需要调用之前写过的代码

这就是为什么我说前两道题是本题的基础

✍️代码实现

//找链表的中间节点
struct listnode* middlenode(struct listnode* head)
{
    struct listnode* slow = head;
    struct listnode* fast = head;
    while (fast != null && fast->next != null)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

//反转链表
struct listnode* reverselist(struct listnode* head)
{
    struct listnode* cur = head;
    struct listnode* prev = null;
    while (cur != null)
    {
        struct listnode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

//牛客这道题不支持用c语言答题
//虽然我们还没有学c++，但是c++是兼容c的
//直接用c的方式写代码即可
class palindromelist
{
public:
    bool chkpalindrome(listnode* head)
    {
        struct listnode* list1 = head;
        struct listnode* mid = middlenode(head);
        struct listnode* list2 = reverselist(mid);
        while (list2 != null)
        {
            if (list1->val != list2->val)
            {
                return false;
            }
            list1 = list1->next;
            list2 = list2->next;
        }
        return true;
    }
};

提交代码：