目录
1、题目介绍
2、解题思路
2.1、暴力破解法
2.2、快慢指针反转链表
1、题目介绍
原题链接: 234. 回文链表 – 力扣(LeetCode)
示例 1:
输入:head = [1,2,2,1]
输出:true
示例 2:
输入:head = [1,2]
输出:false
提示:
- 链表中节点数目在范围[1, 10^5] 内
- 0 <= Node.val <= 9
进阶:你能否用 O(n)
时间复杂度和 O(1)
空间复杂度解决此题?
2、解题思路
判断回文,就是判断是否是对称的。有些朋友对于数组的回文判断非常熟悉,但是对链表的回文判断可能就无从下手了,其实都一样的。有一种非常简单的方式就是将链表转化成数组,然后就是判断该数组是否回文就可以了,这种方式统称暴力破解法,简单粗暴。下面就来先带着大家看一下这道题的暴力破解法。
2.1、暴力破解法
一共为两个步骤:
- 复制链表值到数组列表中。
- 使用双指针法判断是否为回文。
首先按照题目要求的最大大小定义一个大小为100001的整型数组,接着通过循环遍历将链表中每个结点的值取出放入数组中,最后通过两个指针,一个从左一个从右分别判断是否相等,只要遇到一个不相等就返回false,否则当循环结束时返回true。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head){
int arr[100001] = {0},num = 0;
while(head)
{
arr[num] = head->val;
head = head->next;
num++;
}
int i= 0;
int j =0;
for(i = 0,j = num-1; i<j; i++,j--)
{
if(arr[i]!=arr[j])
{
return false;
}
}
return true;
}
时间复杂度:O(n),其中 n 指的是链表的元素个数。
- 第一步:遍历链表并将值复制到数组中,O(n)。
- 第二步:双指针判断是否为回文,执行了 O(n/2) 次的判断,即O(n)。
- 总的时间复杂度:O(2n)=O(n)。
空间复杂度:O(n),其中 n 指的是链表的元素个数,我们使用了一个数组列表存放链表的元素值。
进阶:你能否用
O(n)
时间复杂度和O(1)
空间复杂度解决此题?下面带大家做一下本题的进阶,使用快慢指针反转链表实现空间复杂度为O(1)的算法。
2.2、快慢指针反转链表
整个流程可以分为以下五个步骤:
- 找到前半部分链表的尾节点。
- 反转后半部分链表。
- 判断是否回文。
- 恢复链表。
- 返回结果。
对于第一步找到前半部分链表的尾结点,我们可以计算链表结点个数然后再找到前半部分的尾结点,也可以通过快慢指针一次遍历找到前半部分的尾结点。
慢指针一次走一步,快指针一次走两步,快慢指针同时出发。当快指针移动到链表的末尾时,慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
此时slow就是前半部分的尾结点,而slow的下一个结点就是后半部分的头结点。于是让fast回到slow的next结点处,将后半部分的结点全部反转,然后slow即前半部分的尾结点置空。
紧接着将让slow从head重新出发,fast从最后结点出发,分别向中间结点靠近并判断,只要相等就一直向中间靠近,遇到不相同时直接返回false,否则当循环退出时返回true。
最后在将反转链表还原回去即可。
代码实现:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head){
if(head == NULL || head->next == NULL)
{
return true;
}
struct ListNode* n1 = head;
struct ListNode* n2 = head;
//快慢指针遍历
while(n2->next != NULL && n2->next->next != NULL)
{
n1 = n1->next; //慢指针
n2 = n2->next->next; //快指针
}
n2 = n1->next; //右边第一个
n1->next = NULL;
struct ListNode* n3;
//反转右半边链表
while(n2 != NULL)
{
n3 = n2->next; //n3存放n2的next
n2->next = n1;
n1 = n2;
n2 = n3;
}
//当循环结束时n1所指向的位置就是链表最后一个结点,
n2 = n3 = n1; //将n2和n3指回最后一个节点
n1 = head; //n1回到头结点
bool flag = true;
//判断是否是回文
while(n1 != NULL && n2 != NULL)
{
if(n1->val != n2->val)
{
flag = false;
break;
}
n1 = n1->next;
n2 = n2->next;
}
//还原链表
n2 = n3->next; //n3此时指向最后一个结点,因为反转了链表,n3的next就是上一个结点
n3->next = NULL;
while(n2!=NULL)
{
n1 = n2->next;
n2->next = n3;
n3 = n2;
n2 = n1;
}
return flag;
}
时间复杂度:O(n),其中 n 指的是链表的大小。
空间复杂度:O(1)。我们只会修改原本链表中节点的指向,而在堆栈上的堆栈帧不超过 O(1)。
更多【LeetCode刷题】 推荐:
【LeetCode力扣】86. 分隔链表-CSDN博客
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
文章出处登录后可见!