ListNode* reverseKGroup(ListNode* head, int k) {
//当k为1时不反转,那么将head直接返回
if(k == 1)
return head;
//递归退出条件,当前不够k个节点时,返回head,不反转;够的话,找到下一次递归的头结点
ListNode* post = head;
for(int i = 0; i < k; i++)
{
if(post == NULL)
return head;
post = post->next;
}
//记录head-next,因为其要更新为下次递归回来的节点
ListNode* temp = head->next;
//head->next更新为下次递归的返回头结点,因为head变成了尾节点
head->next = reverseKGroup(post, k);
//记录temp->next,因为temp->next要更新为head
post = temp->next;
temp->next = head;
//开始循环改变节点方向(next)
for(int i = 2; i < k; i++)
{
//先记录要被改变的节点
ListNode* temp1 = post->next;
//改变朝向
post->next = temp;
//更新temp post
temp = post;
post = temp1;
}
//返回当前递归的最后一个节点
return temp;
}
bool isPalindrome(ListNode* head) {
//思想:找到后半段链表,将其反转与前半段比较,所有相同返回true,有不同返回false
//只有一个节点,返回true
if(head->next == NULL)
return true;
//寻找中间节点,奇数个节点时为最中间的节点;偶数时,为中间那对右边的节点
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
//right记录后半段开始比较的首节点
ListNode* right = NULL;
//偶数时确实是slow节点
if(fast == NULL)
right = slow;
//奇数时为slow的下一个节点
else if(fast != NULL && fast->next == NULL)
right = slow->next;
//开始翻转,用pre节点表示反转后链表尾部的空节点
ListNode* pre = NULL;
//循环条件,遍历节点不为空
while(right)
{
//先记录将要丢失的节点
ListNode* temp = right->next;
//反转
right->next = pre;
//更新前一个节点与下一次遍历的节点
pre = right;
right = temp;
}
//反转后的头结点为pre,right节点为空
//遍历翻转后的节点值与前半段值是否相等,存在不相等则输出false;否则最终输出true
while(pre)
{
if(pre->val != head->val)
return false;
pre = pre->next;
head = head->next;
}
return true;
}
vector<int> twoSum(vector<int>& numbers, int target) {
/*超时了!!!
int index1 = 0, index2 = 0;
for(int i = 0; i < numbers.size(); i++)
{
index1 = i;
if(find(numbers.begin(), numbers.end(), target-numbers[i]) != numbers.end())
{
index2 = find(numbers.begin(), numbers.end(), target-numbers[i]) - numbers.begin();
if(index1 != index2)
break;
if(index2 == index1 && index1+1 < numbers.size() && numbers[index1+1] == numbers[index1])
{
index2 = index1+1;
break;
}
}
}
return vector<int>{index1+1, index2+1};
*/
//双指针,因为是有序数组且一定有答案
//对向遍历,初始化为两端
int index1 = 0, index2 = numbers.size()-1;
//当不等的时候继续遍历
while(numbers[index1]+numbers[index2] != target)
{
//如果相加值比目标值小,则说明numbers[index1]较小,index1++
if(numbers[index1]+numbers[index2] < target)
index1++;
//如果相加值比目标值大,则说明numbers[index2]较小,index2--
else
index2--;
}
//注意数组下标题意是从1开始,所以需要索引值+1
return vector<int>{index1+1, index2+1};
}