前言
链表练习题 【234.回文链表】。
回顾链表知识，做题练习。
一、【234.回文链表】题目阅读
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
二、尝试实现
思路
- 直观的使用一个数组，在遍历链表的过程中把值记录下来。最后翻转数组，判断是否相等。
- 翻转数组需要再创建一个副本，可以用双指针法，从两端向中间靠拢，判断值是否相等。
- 这个时间复杂度O(n)，需要遍历链表。空间复杂度O(n)，额外创建数组，数组长度是链表长度。
代码实现【借助数组】
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> arr;
ListNode* cur = head;
while(cur){
arr.push_back(cur->val);//取出值
cur = cur->next;//后移
}
vector<int> temp(arr);
reverse(temp.begin(),temp.end());
if(arr == temp) return true;
return false;
}
};
三、参考学习
学习内容
- 思路一：数组模拟。和二、中的借助数组思路一致。提出优化方向：先求出链表长度n，直接创建长度为n的vector。
- 反转后半部分链表思路：空间复杂度O(1)，原有链表上操作；时间复杂度O(n)，每个节点基本只遍历一次。
- 回文定义，需要从链表的中间开始判断两边是否相等。所以需要定位到中间，并且把链表分成两半。
- 定义快指针，每次走两步；定义慢指针，每次走1步。等快指针到最后一个节点（偶数）或指向空（奇数），慢指针指向位置是第n/2个节点。
- head指针指的是前半截；定义cur2 = slow->next，cur2后面是后半截。
- 把cur2后面链表反转，和head比较。如果总数是偶数，那么前后两节链表长度一样；如果总数是奇数，那么head前半截比后半截多1个。
-
根据参考提供的思路，开始代码实现【反转链表】：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { if(!head->next) return true;//只有一个节点。 ListNode* dummy_node = new ListNode(); dummy_node->next = head; ListNode* fast = dummy_node;//定义快指针，每次走两步 ListNode* slow = dummy_node;//定义慢指针，每次走一步。所以快指针走的路径是慢指针的两倍，当fast到最后时，slow在链表的中间 while(fast && fast->next){ fast = fast->next->next; slow = slow->next; } //while结束时，fast指向最后一个节点（偶数）或最后空节点（奇数），slow指向第n/2个节点 ListNode* cur2 = slow->next; slow->next = nullptr;//中间断开 delete dummy_node;//后面不用虚拟头节点，释放。 //反转后半截，最后的pred就是翻转之后的头结点 ListNode* pred = nullptr; while(cur2){ ListNode* succ = cur2->next; cur2->next = pred; pred = cur2; cur2 = succ; } while(head && pred){ if(head->val == pred->val){ head = head->next; pred = pred->next; }else{ return false; } } return true; } }; -
对比参考代码：区别——
- 记录slow之前的节点，用pred指向。这样后半截从pred->next，即从slow本身之前断开。
- 反转链表直接用reverseList，在主函数之外实现。
思考
“快指针走两步，慢指针走一步”——这个操作，在记录 十二【142. 环形链表 II】中出现过。
特点一：保证快指针走的路程是慢指针走的路程的两倍。可以在求链表中间位置时（本题应用）、环星链表应用；
特点二：如果有环，快指针相对慢指针快一个节点的速度逼近慢指针。
总结
【234.回文链表】中回顾【142. 环形链表 II】的思路题解。
（欢迎指正，转载标明出处）