leetcode 链接:回文链表
《程序员面试代码指南》by 左程云 中相同题目:★★☆☆判断一个链表是否为回文结构(进阶)
题目
编写一个函数,检查输入的链表是否是回文的。
示例:
输入: 1->2
输出: false
输入: 1->2->2->1
输出: true
输入: 1->2->3->2->1
输出: true
解答 & 代码
时间复杂度 O(N),空间复杂度 O(1)
算法流程:
- 如果链表为空或只有一个节点,直接返回 true
- 遍历链表找到中间节点:使用双指针
slow
和fast
,初始时都指向链表第一个节点,- 如果
fast
的后继节点以及后继的后继节点不为NULL
,则fast
走两步,slow
走一步 - 否则,停止遍历,此时
slow
指向的节点就是链表中间节点
- 如果
- 将链表右半部分(中间节点
slow
之后的节点,不含slow
)逆序,将中间节点也就是左半部分链表的最后一个节点 slow 的 next 指向 NULL - 同时遍历左半部分链表 和 逆序后的右半部分链表
- 如果两个节点值不同,则返回 false
- 否则,继续遍历,直到右半部分链表节点遍历结束(因为左半部分长度= 右半部分 or 左半部分长度 - 右半部分长度 = 1)
- 将右半部分链表重新逆序还原,再重新连接左右部分
- 返回 true
```cpp
/**
- Definition for singly-linked list.
- struct ListNode {
- int val;
- ListNode *next;
- ListNode(int x) : val(x), next(NULL) {}
- }; */
// 将链表start到end之间的节点逆序(包含start,不包含end) ListNode reverseList(ListNode start, ListNode end) { ListNode pre = NULL; ListNode cur = start; while(cur != end) { ListNode next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; }
class Solution { public: bool isPalindrome(ListNode* head) { if(head == NULL || head->next == NULL) return true;
// 先找到链表中间节点
ListNode* slow = head;
ListNode* fast = head;
while(fast->next != NULL && fast->next->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
} // 此时 slow 指向中间节点
// 将链表右半部分逆序
ListNode* rightHead = reverseList(slow->next, NULL);
slow->next = NULL; //将左半部分最后指向 NULL
// 依次比较链表左半部分和逆序后的右半部分,如果存在不同,则不是回文序列
ListNode* left = head;
ListNode* right = rightHead;
while(right != NULL)
{
if(left->val != right->val)
return false;
left = left->next;
right = right->next;
}
// 最后将链表右半部分重新逆序回原来的顺序,再与左半部分拼接
rightHead = reverseList(rightHead, NULL);
slow->next = rightHead;
return true;
}
};
执行结果:
执行结果:通过
执行用时:12 ms, 在所有 C++ 提交中击败了 94.69% 的用户 内存消耗:13.4 MB, 在所有 C++ 提交中击败了 56.47% 的用户 ```