题目链接
实现思路


代码实现
/**
* 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:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
ListNode* next = cur -> next;
cur -> next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
/**
* 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:
vector<ListNode*> reverse(ListNode* head, ListNode* next) {
ListNode* pre = next;
ListNode* cur = head;
while (cur != next) {
ListNode* nextNode = cur -> next;
cur -> next = pre;
pre = cur;
cur = nextNode;
}
return {pre, head}; // pre是反转之后的头节点,head是反转之后的尾节点
}
ListNode* reverseKGroup(ListNode* head, int k) {
int cnt = 0;
ListNode* cur = head;
ListNode* preHead = new ListNode(-1);
preHead -> next = head;
ListNode* pre = preHead;
while (cur) {
cnt++;
if (cnt % k == 0) {
cnt = 0;
vector<ListNode*> res = reverse(pre->next, cur->next);
pre->next = res[0];
cur = res[1];
pre = cur;
}
cur = cur -> next;
}
return preHead -> next;
}
};
/**
* 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:
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* next = cur -> next;
cur -> next = pre;
pre = cur;
cur = next;
}
return pre;
}
bool isPalindrome(ListNode* head) {
if (head -> next == nullptr) return true;
ListNode* preHead = new ListNode();
preHead -> next = head;
ListNode* slow = preHead;
ListNode* fast = preHead;
while (fast != nullptr && fast -> next != nullptr) {
slow = slow -> next;
fast = fast -> next -> next;
}
// 反转slow->next到tail的部分
ListNode* head1 = slow -> next;
head1 = reverse(head1);
ListNode* cur = head;
ListNode* cur1 = head1;
while (cur1) {
if (cur -> val != cur1 -> val) {
return false;
}
cur = cur -> next;
cur1 = cur1 -> next;
}
return true;
}
};