c++重新排序单链表

Question

嗨，我正试图为单链表重新排序节点的代码，以便:

L1, L2, L3→…→Ln对L1→Ln→L2→ln1→L3→ln2…

因此，我试图通过在列表末尾找到节点并将该节点设置为当前节点的下一个节点，然后通过将当前节点设置为当前节点的下一个节点来完成循环。

#include <cstdlib>
#include <iostream>
using namespace std;
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) {}
};
ListNode* newNode(int x){
ListNode* temp = new ListNode;
temp->val = x;
temp->next = NULL;
return temp;
}
void printlist(ListNode* head)
{
while (head != NULL) {
cout << head->val << " ";
if (head->next)
cout << "-> ";
head = head->next;
}
cout << endl;
}
void reorderList(ListNode* head){
ListNode *curr = head;
ListNode *temp=head;
ListNode *last=NULL;
while(curr->next != NULL){
while(temp->next != NULL){
temp=temp->next;
last=temp;
}
curr->next=last;
last->next=curr->next->next;
curr=curr->next->next;
temp=curr->next;
}
}
int main(int argc, char** argv) {
ListNode* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);

printlist(head); // Print original list
reorderList(head); // Modify the list
printlist(head); // Print modified list
return 0;
}

到目前为止，在显示原始列表之后，程序停止运行，说运行失败。我在理解单链表时遇到了一些问题，我不知道我做错了什么。

Answer 1

我已经修改了你的代码，以显示正确的答案:

#include <iostream>
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 ) {}
};
void printlist( ListNode* head )
{
while( head != nullptr ) {
std::cout << head->val << " ";
if( head->next )
std::cout << "-> ";
head = head->next;
}
std::cout << std::endl;
}
void reorderList( ListNode* head ) {
ListNode* pf = head;
ListNode* pt = nullptr;
ListNode* tmp = nullptr;
while( true )
{
// find n-1 node
tmp = pf;
while( tmp && tmp->next && tmp->next->next )
tmp = tmp->next;
// check to see n-1 node is not equal to the first node
if( tmp == pf )
break;
// reorder
pt = tmp;
tmp = pf->next;
pf->next = pt->next;
pt->next->next = tmp;
pf = tmp;
pt->next = nullptr;
}
}
int main( int argc, char** argv ) {
ListNode* head = new ListNode( 1 ); 
head->next = new ListNode( 2 );
head->next->next = new ListNode( 3 );
head->next->next->next = new ListNode( 4 );
head->next->next->next->next = new ListNode( 5 );
head->next->next->next->next->next = new ListNode( 6 );
printlist( head ); // Print original list
reorderList( head ); // Modify the list
printlist( head ); // Print modified list
return 0;
}

，结果如下:

1 -> 2 -> 3 -> 4 -> 5 -> 6                                                                                              
1 -> 6 -> 2 -> 5 -> 3 -> 4  

Answer 2

你的问题可能有很多解决方案。我只是修改了你的逻辑，并添加了一些评论，可以帮助你理解。快乐链表编码。

#include <cstdlib>
#include <iostream>

using namespace std;
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) {}
};
ListNode* newNode(int x){
ListNode* temp = new ListNode;
temp->val = x;
temp->next = NULL;
return temp;
}
void printlist(ListNode* head)
{
while (head != NULL) {
cout << head->val << " ";
if (head->next)
cout << "-> ";
head = head->next;
}
cout << endl;
}
void reorderList(ListNode* head){
ListNode *curr = head;
ListNode *temp=head;
ListNode *last=NULL,*prev;
while(curr->next != NULL){

while(temp->next != NULL){
//Prev variable is being used for remove last node connection from it previous node
// For example 1->2->3
// We need to remove 2->3 connection before adding 1->3
// Otherwise it will create cycle i.e 1->3->2->3->2....
prev = temp;
temp=temp->next;
last=temp;

}
// If node number is even this condition will check adding mid+1 node twice
if(last==NULL) {
break;
}
temp = curr->next;
curr->next=last;
last->next=temp;
curr=curr->next->next;
temp=curr->next;
// Removing last node connection from it previous node
prev->next = NULL;
last = NULL;
}
}
int main(int argc, char** argv) {
ListNode* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
//head->next->next->next->next->next = newNode(8);

printlist(head); // Print original list
reorderList(head); // Modify the list
printlist(head); // Print modified list
return 0;
}