C++ 重新排序单链表

Question

您好，我正在尝试为单向链表编写代码以重新排序节点，以便：

L1->L2->L3->...->Ln 到 L1->Ln->L2->Ln-1->L3->Ln-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;
    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

您的问题可能有多种解决方案。我只是修改了您的逻辑并添加了可以帮助您理解的评论。快乐 link 列表编码。

#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;
}

C++ 重新排序单链表

C++ reordering Singly Linked List

c++

linked-list

reorderlist

data-structures

singly-linked-list