文章目录
1. 题目介绍2. 思路分析3. 代码实现
1. 题目介绍
链接: link 这道题呢是让我们判断一个链表是否是回文结构。但是题目要求设计一个时间复杂度为O(n)，额外空间复杂度为O(1)的算法。 所以如果我们想把链表的值存到一个数组中再去判断就不可行了。
2. 思路分析
那对于这道题呢比较好的一个思路是这样的：
不是要判断链表是否是回文结构嘛。 回文结构的话就是从中间分开，两边是对称的嘛（比如：1，2 | 2，1），当然如果是奇数个结点的话就是以中间结点为对称轴（比如：1 2 3 2 1）。 那我就可以这样做： 找到链表的中间结点，将从中间结点开始往后的部分进行逆置（如果是偶数个有两个中间结点就从第二个开始）。 后半部分逆置之后，我们比较这两部分是否相同，如果相同，他就是回文结构。
单凭上面的文字大家可能还不是特别清楚，下面我们来画个图分析一下：
就以1 2 2 1为例： 首先找到中间结点是2（第二个2），这里找链表中间结点我们前面就做过这个题，到时候就可以直接用。 那逆置之后就是这样 链表逆置之前我们也写过对应的OJ题，待会也可以直接用。那逆置之后我们可以拿到逆置之后后半部分链表的头指针。 同时题目给了我们原链表的头指针。 那然后我们就可以同时从这两个头指针开始往后遍历，依次两个比较每对结点，如果某次比较不相同，那就不是回文结构，直接返回false。 如果是回文结构，就一直向后比，所以肯定要写成循环，那循环什么时候结束呢？ ，后半部分链表逆置之后最后一个结点指向空，所以如果遍历到rhead为空，还没返回false，那就是全部相同，他就是回文结构，此时循环结束，返回true。
但是上面我们分析的是偶数个结点的情况，如果是奇数个，还适用吗？
，是可以的。 以1 2 3 2 1为例 逆置后半部分之后是这样子。 然后还是两两比较，1 2相等，2 2 相等 此时我们看到对于前半部分链表来说，到2就遍历完了。后半部分虽然每遍历完，但是奇数个的话，他最后剩下的那个就是原链表最中间的那个结点。 那中间结点的左右两部分都相等了，其实已经证明是回文了，就可以结束了。 所以逆置之后是不是应该把前半部分的尾结点next置空，这样只要有一个链表走到空就结束，就是回文。 可以置空，但是其实没必要。而且要置空的话还得保存一下中间结点的前一个，怪麻烦的。 我们看到，不置空的话，此时前半部分的尾结点（这里是2）指向谁？ 就是原链表的中间结点，所以可以继续向后比较，自己跟自己比，肯定相同，那再往后后半部分链表就走到空了。循环结束，返回true。 如果不是回文链表，中间比较的时候不相同就直接返回false了。 所以不需要将前半部分尾结点next置空，循环结束的条件就是后半部分链表走到空。
3. 代码实现
那我们来写一下代码：
这两个函数我就直接拷贝之前我们写过的代码了，之前的文章我们都讲过，大家可以去看。
就搞定辽！
提交一下： 过啦！
class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
struct ListNode* tmp = NULL;
while (cur) {
//保存下一个的地址
tmp = cur->next;
//头插
cur->next = newhead;
newhead = cur;
cur = tmp;
}
return newhead;
}
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool chkPalindrome(struct ListNode* A) {
struct ListNode* midnode=middleNode(A);
struct ListNode* rhead=reverseList(midnode);
while(rhead)
{
if(A->val!=rhead->val)
return false;
A=A->next;
rhead=rhead->next;
}
return true;
}
};
相关链接
发表评论