不交换节点的链接列表

Question

我正在尝试通过使用列表中的多个链接对列表进行升序排序。这是我的结构：

typedef struct NODE{
   int    value;
   double key1;
   double key2;
   struct NODE* next;
   struct NODE* sort1;
   struct NODE* sort2;
} Node;

我希望对列表进行排序，因此下一个链接是原始顺序，sort1链接是key1值的顺序，sort2链接是key2值的顺序。我要尝试的方法是类似冒泡排序的方法，其中程序采用下一个链接，并按key1和key2的升序生成sort1和sort2链接。

这是我的排序功能：

void sort_list_key1(Node * start){

   int swapped; 
   Node *ptr1; 
   Node *lptr = NULL; 

   /* Checking for empty list */
   if (start == NULL) 
       return; 

   do{ 

      swapped = 0; 
      ptr1 = start; 
      while (ptr1->sort1 != lptr){ 
        if (ptr1->key1 > ptr1->sort1->key1) {  
            swap_list(ptr1 , ptr1->sort1); 
            swapped = 1; 
        } 
        ptr1 = ptr1->sort1; 
      } 
      lptr = ptr1; 
   } 
   while (swapped); 
}

这里是swap_list函数：

void swap_list(Node *p1, Node *p2){ 

  Node *temp = p1->sort1;  
  p1->sort1 = p2->sort1;  
  p2->sort1 = temp;
} 

谢谢

编辑：

我无法更改结构，因为它是家庭作业的一部分。我有指针：

Node * head;
Node * sort1;
Node * sort2;

主要填充该结构的值是通过以下方式随机生成的：

Node * random_list(Node *head) {

   Node * new_node;
   new_node  = (Node *) malloc(sizeof(Node));

   new_node->value = rand() % 10;
   new_node->key1  = rand_double(10.0 , 50.0);
   new_node->key2  = rand_double(50.0 , 90.0);     
   new_node->sort1 = NULL;
   new_node->sort2 = NULL;
   new_node->next  = head;

   head = new_node;

   return head;
}

链表是由for循环创建的，该循环循环播放用户指定的大于5的次数。如何使用sort1和sort2链接对列表进行排序，而不更改所生成的下一个链接的顺序？

Answer 1

如何在不更改生成的下一个链接的顺序的情况下使用sort1和sort2链接对列表进行排序？

只要您的排序不会创建新的节点（它不应该）-实际上这不是问题。您只需忽略“下一个”链接，而只关注用于排序的链接。要了解原因，请考虑使用next链接遍历列表-从头到下一个节点，依此类推，以此类推；它有一定顺序吧？现在假设您已经替换了所有的sort1链接（不管用什么）；这会使用next链接更改遍历吗？它不会，它会以完全相同的顺序发生。