正如标题所说，本文会图文详细解析三道单链表OJ题，分别为：
- 反转链表 （简单）
- 链表的中间节点 （简单）
- 链表的回文结构 （较难）
把他们放在一起讲的原因是： 反转链表 和 链表的中间节点 是 链表的回文结构 的基础
为什么这样说？请往下看：
目录
1. 反转链表
LeetCode链接：206. 反转链表 - 力扣（LeetCode）
💭做题思路
- 遍历链表，改变每个节点的链接方向，使其链向前节点
- 如果是第一个节点，使其链向 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. 链表的中间节点
LeetCode链接：876. 链表的中间结点 - 力扣（LeetCode）
💭做题思路
- 快慢指针
- 搞两个指针，一个叫 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;
}
};
提交代码：
成功通过
怎么样，大家看到这里把这三道题弄懂了吗？如果有问题可以在评论区留言哦 :D
本文完