回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
思路
将值复制到数组中后用双指针法
这属于是暴力法了，思路就跟名字一样直接，性能也很垃圾，权当无限制刷题时的方法好了
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> nums;
ListNode* cur = head;
while(cur){
nums.push_back(cur->val);
cur = cur->next;
}
for(int left = 0, right = nums.size() - 1; left < right; ++left, --right){
if(nums[left] == nums[right]) continue;
return false;
}
return true;
}
};
快慢指针
这个比上面的方法高级一些
首先，使用快慢指针（快指针比慢指针多走一步）遍历一遍链表，当快指针到nullptr时，慢指针就走到了链表中心位置
如果节点个数是偶数那就是前半部分
这个时候调用翻转链表的函数将中间节点之后的部分全部翻转
然后重新创建两个指针，一个指向链表的head，一个指向前面找到的中点，同时向后遍历，确保链表是回文的
最后将被翻转的部分复原（因为我们只是判断，不能修改原有的数据）
class Solution {
private:
ListNode* findFirstPartEnd(ListNode* head){//寻找链表前半部分
ListNode* fast = head;
ListNode* slow = head;
while(fast->next != nullptr && fast->next->next != nullptr){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode* reverseList(ListNode* head){//链表翻转
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur){
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
public:
bool isPalindrome(ListNode* head) {
if(head->next == nullptr) return true;
//找前半部分的末尾
ListNode* firstHalfEnd = findFirstPartEnd(head);
ListNode* secondHalfStart = reverseList(firstHalfEnd->next);//注意，是给下一个
ListNode* p1 = head;
ListNode* p2 = secondHalfStart;
while(p2 != nullptr){
if (p1->val != p2->val) return false;
p1 = p1->next;
p2 = p2->next;
}
//还原链表
firstHalfEnd->next = reverseList(secondHalfStart);
return true;
}
};
服了，这个实现性能一样垃圾，还白写这么多代码
呕呕呕
删除链表的中间节点
给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
示例 1：
输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。
示例 2：
输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。
示例 3：
输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。
提示：
链表中节点的数目在范围 [1, 105] 内
1 <= Node.val <= 105
思路
和回文链表中定位到链表中间位置的操作类似
但是，这里还需要一个额外的指针pre，用来指向slow指针的前一个位置
因为我们要删除的是slow位置的节点，所以得拿到其前一个位置的指针
这里你可能会想，那按照删除倒数第n个节点那样，先让fast移动n+1行不行
理论上是行的，但是得计算区分奇偶，有点麻烦，算啦
代码
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
if (head->next == nullptr) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
ListNode* pre = nullptr;//指向slow前一个节点，为的是把slow指向的节点删掉
while (fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
pre->next = pre->next->next;
return head;
}
};