对于输入1->2->2->4->5->6->7->8
我的输出是8 7 6 5 4 2 2 1，但我不知道为什么
问题链接如下：https://practice.geeksforgeeks.org/problems/reverse-a-linked-list-in-groups-of-given-size/1
在给定大小的组中反转链表
给定大小为N的链表。任务是反转链表中的每个k节点(其中k是函数的输入)。如果节点的数量不是k的倍数，那么遗漏的节点最终应被视为一个组，并且必须颠倒(请参见示例2进行说明)。
示例1:
Input:
LinkedList: 1->2->2->4->5->6->7->8
K = 4
Output: 4 2 2 1 8 7 6 5
Explanation:
The first 4 elements 1,2,2,4 are reversed first
and then the next 4 elements 5,6,7,8. Hence, the
resultant linked list is 4->2->2->1->8->7->6->5.
示例2:
Input:
LinkedList: 1->2->3->4->5
K = 3
Output: 3 2 1 5 4
Explanation:
The first 3 elements are 1,2,3 are reversed
first and then elements 4,5 are reversed.Hence,
the resultant linked list is 3->2->1->5->4.
您的任务：
您不需要读取输入或打印任何内容。您的任务是完成函数reverse()，该函数应反转大小为k的组中的链表，并返回修改后的链表的头。
预期时间复杂度：O(N)
预计辅助空间:O(1)
限制条件：
1<=N<=104
1<=k<=N
我下面的代码：
//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node* next;
node(int x){
data = x;
next = NULL;
}
};
/* Function to print linked list */
void printList(struct node *node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("n");
}
// } Driver Code Ends
/*
Reverse a linked list
The input list will have at least one element
Return the node which points to the head of the new LinkedList
Node is defined as
struct node
{
int data;
struct node* next;
node(int x){
data = x;
next = NULL;
}
}*head;
*/
class Solution
{
node* reverseHelper(node* head){
node* pre = NULL;
node* curr = head;
while(curr!=NULL){
node* nextTocurr = curr->next;
curr->next = pre;
pre = curr;
curr = nextTocurr;
}
return pre;
}
public:
struct node *reverse (struct node *head, int k)
{
// Complete this method
if(head==NULL|| head->next==NULL){
return head;
}
int count = 0;
node* tail = head;
while(count<k || tail->next!=NULL){
tail = tail->next;
count++;
}
node* head2 = tail->next;
tail->next = NULL;
node* ans = reverseHelper(head);
head->next = reverse(head2,k);
return ans;
}
};
//{ Driver Code Starts.
/* Drier program to test above function*/
int main(void)
{
int t;
cin>>t;
while(t--)
{
struct node* head = NULL;
struct node* temp = NULL;
int n;
cin >> n;
for(int i=0 ; i<n ; i++)
{
int value;
cin >> value;
if(i == 0)
{
head = new node(value);
temp = head;
}
else
{
temp->next = new node(value);
temp = temp->next;
}
}
int k;
cin>>k;
Solution ob;
head = ob.reverse(head, k);
printList(head);
}
return(0);
}
// } Driver Code Ends
问题就在这个循环中：
int count = 0;
while(count<k || tail->next!=NULL){
它有两个问题：
循环将一直持续到列表的末尾，因为第二个条件将为true，直到到达该末尾。逻辑OR(
||)应该是逻辑AND(&&)，因为您希望两个条件都为true，而不仅仅是一个。当前一点被校正时，循环仍然会迭代一次太多，因为
head节点已经被认为包括在"循环"中；切片"；。通过初始化count=1进行校正。
有了这两个更正，您的代码将按预期工作。