题目练习之链表那些事儿（续集）
这一篇博客也来看看和链表有关的题目~
反转链表
反转链表： https://leetcode.cn/problems/reverse-linked-list/description/
这个题目已经十分清晰了，那我们可以怎么做呢？
结合前面单链表的知识点，我们很容易可以想到第一个思路。
思路1
创建一个新链表，将原来的链表的结点进行头插
为了方便我们使用，我们同样将结点进行重命名
代码实现：
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
//创建新链表
ListNode* newHead = NULL;
ListNode* newTail = NULL;
//遍历原来的链表头插
ListNode* pcur = head;
while (pcur)
{
//如果新链表为空
//头结点和尾结点就是当前的结点
if (newHead == NULL)
{
newHead = newTail = pcur;
}
//新链表不为空进行头插
else
{
//当前结点下一个节点指向新链表的头结点
pcur->next = newHead;
//当前结点成为新链表头结点
newHead = pcur;
}
//继续遍历
pcur = pcur->next;
}
//新链表尾结点的下一个结点置为空
newTail->next = NULL;
//返回新链表
return newHead;
}当我们写出代码提交的时候，它说运行时间超出限制
在OJ平台上不好看出问题我们使用VS进行调试一下去发现问题。
测试代码如下：
//测试问题代码
#include<stdio.h>
#include<stdlib.h>
struct ListNode
{
int val;
struct ListNode* next;
};
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
//特殊处理链表本来就为空
if (head == NULL)
{
return NULL;
}
//创建新链表
ListNode* newHead = NULL;
ListNode* newTail = NULL;
//遍历原来的链表头插
ListNode* pcur = head;
//count记录进入循环几次
int count = 0;
while (pcur)
{
count++;
//如果新链表为空
//头结点和尾结点就是当前的结点
if (newHead == NULL)
{
newHead = newTail = pcur;
}
//新链表不为空进行头插
else
{
//当前结点下一个节点指向新链表的头结点
pcur->next = newHead;
//当前结点成为新链表头结点
newHead = pcur;
}
//继续遍历
pcur = pcur->next;
}
//新链表尾结点的下一个结点置为空
newTail->next = NULL;
//返回新链表
return newHead;
}
void sListPrint(ListNode* head)
{
ListNode* pcur = head;
while (pcur)
{
printf("%d->", pcur->val);
pcur = pcur->next;
}
printf("NULL\n");
}
int main()
{
//手动创建链表
ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
node1->val = 1;
node2->val = 2;
node3->val = 3;
node4->val = 4;
sListPrint(node1);
ListNode* newList = reverseList(node1);
sListPrint(newList);
return 0;
}
我们会发现pcur和newHead一直在1和2之间循环，没有往后面走了，这是为什么呢？
事实上，在头插时使用pcur进行操作，已经改变了pcur的指向，pcur下一个结点永远是newHead，那么pcur也就走不到NULL，也就进入了死循环，这就是为什么刚刚代码超出时间限制，死循环了。
解决方案：使用一个结点pos保存pcur，pcur直接往后面走。
正确代码（使用打印直观观察）
#include<stdio.h>
#include<stdlib.h>
struct ListNode
{
int val;
struct ListNode* next;
};
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
//特殊处理链表本来就为空
if (head == NULL)
{
return NULL;
}
//创建新链表
ListNode* newHead = NULL;
ListNode* newTail = NULL;
//遍历原来的链表头插
ListNode* pcur = head;
while (pcur)
{
//易错点
//使用pos保存pcur
//避免后面指向改变
ListNode* pos = pcur;
//pcur直接继续遍历
pcur = pcur->next;
//如果新链表为空
//头结点和尾结点就是当前的结点
if (newHead == NULL)
{
newHead = newTail = pos;
}
//新链表不为空进行头插
else
{
//当前结点下一个节点指向新链表的头结点
pos->next = newHead;
//当前结点成为新链表头结点
newHead = pos;
}
}
//新链表尾结点的下一个结点置为空
newTail->next = NULL;
//返回新链表
return newHead;
}
void sListPrint(ListNode* head)
{
ListNode* pcur = head;
while (pcur)
{
printf("%d->", pcur->val);
pcur = pcur->next;
}
printf("NULL\n");
}
int main()
{
//手动创建链表
ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
node1->val = 1;
node2->val = 2;
node3->val = 3;
node4->val = 4;
sListPrint(node1);
ListNode* newList = reverseList(node1);
sListPrint(newList);
return 0;
}
我们的代码是没有问题的，那么我们看看代码在OJ平台上是不是可以通过
提交通过~
那么有没有更加简单的方法呢？我们一起来看看思路2
思路2
1.创建三个指针n1、n2、n3 2.最开始n1指向NULL，n2指向head，n3指向n2的下一个结点 3.遍历链表，每一次进入循环n2的下一个结点指向n1， n1走到n2的位置，n2走到n3的位置，n3走到n3后面一个位置，直到n2为空结束循环。 这一个思路的好处在于没有创建新链表，直接在原来链表进行操作改变结点指向，是不是更加地巧妙呢！
代码实现：
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
//特殊处理链表为空
if (head == NULL)
{
return NULL;
}
//创建三个指针
ListNode* n1, *n2, *n3;
n1 = NULL;
n2 = head;
n3 = n2->next;
ListNode* pcur = head;
//遍历链表
while (n2)
{
n2->next = n1;
//n1、n2、n3往后面走
n1 = n2;
n2 = n3;
if (n3)//n3先为空，判断一下避免对空指针解引用
n3 = n3->next;
}
//返回链表
return n1;
}
代码通过，这个方法更加巧妙，没有创建新链表，在原来链表改变指向就成功了。
接下来看看反转链表的运用
返回倒数第k个结点
返回倒数第k个结点：. - 力扣（LeetCode）
我们知道单链表是单向的，不能向数组那样使用下标从后面往前面走，这里这个题我们是不是就可以反转链表然后再找到我们想要的结点。
思路
反转链表，往后面走k步，得到结点数据
int kthToLast(struct ListNode* head, int k)
{
//反转链表
struct ListNode* n1, * n2, * n3;
n1 = NULL, n2 = head, n3 = n2->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
{
n3 = n3->next;
}
}
struct ListNode* pcur = n1;//逆置的头结点
//已经在第一个结点//遍历次数减少1
int count = k - 1;
while (count--)
{
pcur = pcur->next;
}
return pcur->val;
}
相信有了前面的基础，这里的代码so easy！！
链表的中间结点
链表的中间结点：https://leetcode.cn/problems/middle-of-the-linked-list/description/
这个题我们可以怎么办呢？这里依然提供两个思路
思路1
既然是中间结点我们是不是可以直接第一次循环求链表结点的总个数，除2就可以得到中间位置，再一次循环找到中间位置结点，这一个思路就需要两个循环实现。
代码实现：
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
//第一次循环遍历知道结点总个数
int longList = 0;
ListNode* pcur1 = head;
while (pcur1)
{
longList++;
pcur1 = pcur1->next;
}
//找到中间结点
//例：（结合题目中间结点的概念）
// 总个数：5 奇数 mid = 2
// 总个数：6 奇数 mid = 3
int mid = longList / 2;
//这里mid代表往后面走几次到中间结点
//类似下标理解
//第二次循环找到并且返回中间结点
ListNode* pcur2 = head;
while (mid--)
{
pcur2 = pcur2->next;
}
//返回中间结点
return pcur2;
}
成功通过，这里使用了两次循环，有没有只需要使用一次循环的方法呢？也就是我们的思路2
思路2
快慢指针法 定义两个指针slow=fast=head，一个是快指针fast每次走两步，一个是慢指针slow每次走一步，当fast为NULL（偶数）fast->next为NULL（奇数）时，循环结束，返回慢指针。 原理：2*慢指针==快指针
画图理解：
代码实现：
//2.快慢指针
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
//创建两个指针
ListNode* slow, * fast;
slow = fast = head;
while (fast && fast->next)
//顺序不可以换，避免空指针解引用
//&&会有短路现象（如果&&左边表达式成立，右边就不会执行运算）
{
//慢指针走一步
slow = slow->next;
//快指针走两步
fast = fast->next->next;
}
//返回慢指针
return slow;
}
成功通过，这里代码也就更加简便，是不是十分巧妙~~~
链表的回文结构
链表的回文结构 ： https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
在C语言学习阶段，我们知道数据回文这样一种特殊的结构形式，比如12321、1221、abccba，这些都是回文结构的形式，我们可以把它们理解成是一种对称结构。
这里提到了链表的回文结构，我们一起来看看~
题目是想要我们判断一个链表是不是回文结构，我们知道链表在物理结构上并不是对称的，我们不能使用像数组判断是不是回文结构的方式（使用下标，从下标最小处和下标最大处向中间靠近，判断是不是回文结构），那我们可以怎么办呢？我们是不是把这一个复杂问题简单化，接下来看看思路1~
思路1
我们可以把这一个复杂问题简单化，这里面链表的长度已经给出小于900，那么我们是不是就可以创建一个900的数组来保存链表里面的数据，再使用数组判断回文的方式来进行判断。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
//创建数组
int arr[900] = { 0 };
ListNode* pcur = A;
int i = 0;
while (pcur)
{
//遍历链表，赋值数据到数组
arr[i++] = pcur->val;
pcur = pcur->next;
}
//这个时候i就是链表结点个数
int left = 0;
int right = i - 1;
while (left < right)
{
if (arr[left] != arr[right])
{
//不相等就不是回文结构
return false;
}
left++;
right--;
}
return true;
}
};
提交通过了，这里的代码通过我们复杂问题简单化就十分简单了，我们来看看下面的思路~
思路2
创建新链表，将原来的链表反转成为新链表，遍历两个链表比较判断是不是回文结构
class PalindromeList {
public:
ListNode* reverseList(ListNode* head)
{
//特殊处理链表为空
if (head == NULL)
{
return head;
}
//创建三个指针
ListNode* n1, * n2, * n3;
n1 = NULL;
n2 = head;
n3 = n2->next;
ListNode* pcur = head;
//遍历链表
while (n2)
{
n2->next = n1;
//n1、n2、n3往后面走
n1 = n2;
n2 = n3;
if (n3)//n3先为空，判断一下避免对空指针解引用
n3 = n3->next;
}
//返回链表
return n1;
}
bool chkPalindrome(ListNode* A)
{
//新链表就是原来的链表反转
ListNode* newList = reverseList(A);
//遍历两个链表，比较结点元素是否相等
ListNode* pcur1 = A;
ListNode* pcur2 = newList;
while (pcur1) {
//有一个不相等就不是回文结构
if (pcur1->val != pcur2->val) {
return false;
}
//往后面遍历
pcur1 = pcur1->next;
pcur2 = pcur2->next;
}
//遍历结束，全部相等是回文结构
return true;
}
};
提交成功~
这里由于牛客网只提供4种方式来写这个代码，所以我们使用C++来实现代码，当然C++是包含C语言的，同时我们也可以看到struct ListNode在C++中只需要使用ListNode就可以了，可以看出C++的语法更加完善。
思路3
1.找到中间结点 2.反转以中间结点为头的链表部分 3.从头结点和中间结点开始遍历比较，判断是否为回文结构。
代码实现：
class PalindromeList {
public:
//找中间结点成员函数
//快慢指针
ListNode* midNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
//反转链表函数
ListNode* reverseList(ListNode* head) {
//特殊处理链表为空
if (head == NULL) {
return head;
}
//创建三个指针
ListNode* n1, * n2, * n3;
n1 = NULL;
n2 = head;
n3 = n2->next;
ListNode* pcur = head;
//遍历链表
while (n2) {
n2->next = n1;
//n1、n2、n3往后面走
n1 = n2;
n2 = n3;
if (n3)//n3先为空，判断一下避免对空指针解引用
n3 = n3->next;
}
//返回链表
return n1;
}
//判断回文结构函数
bool chkPalindrome(ListNode* A) {
//找到中间结点
ListNode* mid = midNode(A);
//反转以中间结点为头的链表
ListNode* pcur2 = reverseList(mid);
//从头结点和中间结点开始遍历比较，判断是否为回文结构
ListNode* pcur1 = A;
while (pcur2) { //中间结点往后面遍历到空结束
if (pcur1->val != pcur2->val) {
return false;
}
pcur1 = pcur1->next;
pcur2 = pcur2->next;
}
return true;
}
};
提交通过~这个代码是不是更加巧妙呢？代码世界也是十分有趣呢！
♥♥♥本篇博客内容结束，期待与各位未来的优秀程序员交流，有什么问题请私信♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
腾讯云开发者
