我有两个反转链接列表的实现。第一个定义为Node * Reverse(Node * head,int k)方法。此方法反转链接列表的每k个备用子组。逆向链接列表的每个k个节点
Example: Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3
Output: 3->2->1->6->5->4->8->7->NULL
其他实现定义为kAltReverse(Node * head,int k)。该函数反转每个k节点,然后跳过下一个k节点,并为下一个k节点执行相同的操作。
Example Input: 1->2->3->4->5->6->7->8->9->NULL and k = 3
Output: 3->2->1->4->5->6->9->8->7->NULL
这里是我的代码以节点结构的定义和两种功能的倒退与kAltReverse
// This is the definition of node structure
typedef struct container{
int data;
struct container *next;
} Node;
Node *reverse(Node *head, int k){
Node *temp = head;
Node *curr = head;
Node *prev = NULL;
Node *next = NULL;
int count = 0;
// Reverses the first k nodes iteratively
while (curr != NULL && count < k){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
// Recursively linking the head of the list to next reversed list.
if (next != NULL) temp->next = reverse(next,k);
return prev;
}
Node *kAltReverse(Node *head, int k){
Node *temp = head;
Node *curr = head;
Node *prev = NULL;
Node *next = NULL;
int count = 0;
// Reverse the first k node of the linked list
while (curr != NULL && count < k){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
// Now head points to the kth node. So change next of head to (k+1)th node
if (head != NULL) temp->next = curr;
count = 0;
//Move the pointer node so as to skip next k nodes.
while(curr != NULL && count < k-1){
curr = curr->next;
count++;
}
// Recursively call for the list starting from curr->next.
// And make rest of the list as next of first node.
if (curr != NULL) curr->next = kAltReverse(curr->next,k);
return prev;
}
int main(){
Node *head1 = NULL;
/* Insert function is a function for pushing the element in stack
like fashion on to the list*/
insertFirst(&head1, 6);
insertFirst(&head1, 4);
insertFirst(&head1, 3);
insertFirst(&head1, 2);
insertFirst(&head1, 1);
insertFirst(&head1, 5);
// So the list will be 5->1->2->3->4->6->NULL
// Now when I call the functions Reverse and kAltReverse I get undesired
// output.
printlist(head1);
Node *Reverse = reverse(head1, 2);
printlist(Reverse);
Node *kAlt1 = kAltReverse(head1,2);
printlist(kAlt1);
return 0;
}
这是我得到的输出是:
5 1 2 3 4 6 // This is the original list
1 5 3 2 6 4 // This is the output given by Reverse method
3 5 2 6 4 // This is the output given by kAltReverse method
但是,如果我给他们打电话分开并注释掉其他方法,我得到所需的输出即
Output from reverse: 1 5 3 2 6 4 // This is correct
Output form kAltReverse as: 1 5 2 3 6 4 // This is correct too.
所以他们分开工作,但不在一起。
我无法弄清楚为什么会发生这两个同时被调用。另一方面,当这些方法被相互独立地调用时,它们会产生适当的输出。请帮忙。
这两个函数*修改*列表,所以如果您第一次调用'reverse',当您调用'kAltReverse'时,您不再有原始列表。 –
但我只传递指针的值,即它是按值调用,而不是通过引用调用。在这两个代码头都没有触动,这些功能只是使用头部来获得地址,然后独立完成所有工作。但你是对的,他们正在修改列表,理由超出了我的理解范围。 –
C不支持_methods_,只有_functions_ – Olaf