当我被告知“对单链表进行排序”时，预期会发生什么？

Question

它可能是出于迂腐的目的，但不是家庭作业。我有以下关于“对单链表进行排序”（任何类型的列表）的问题，假设对于这个问题，我们希望按每个节点中的值的升序进行排序。

这个问题是否期望我通过交换列表中每个节点的值来对列表进行排序，以便这些值按某种顺序（升序/降序）。这里节点的原始值（排序之前）将被更改以反映排序后的列表。这里返回相同的早期头指针，但现在其中包含最小的元素，这可能与其早期元素不同。

就像我下面的C代码一样（下面的代码可能无法按原样编译，但我可以正常工作。在这里发布作为说明以澄清我的观点）：

struct lnk_lst 
{
   int val;
   struct lnk_lst *next;
};

main()
{

  //Assume curr is the head node of the singly linked list created with some values
curr = llist_bubble_sort(curr);

}

struct lnk_lst* llist_bubble_sort(struct lnk_lst *lst)
{
    int i,n=0,tmpint;
    struct lnk_lst *tmp=lst,*tmp2=lst;

    while(tmp->next)
    {
        lst = tmp2;
        while(lst->next)
        {
            if(lst->val > lst->next->val)
            {
                tmpint = lst->val;
                lst->val = lst->next->val;
                lst->next->val = tmpint;
            }
            lst = lst->next;
        }
        tmp = tmp->next;
    }

    return tmp2;

}

或者

是否期望指向具有最小元素的节点的指针（假设升序）原始排序被移动为新的头节点，然后具有下一个最小元素的节点链接到头节点，依此类推，使得列表完全重新排序，现在返回的头节点不是同一个指针和之前一样。

如果列表排序的解释是这一秒，那么我必须看看如何在代码中实现这个想法。

Answer 1

链接列表背后的整个想法是可以更改链接而不影响内容。更改指针有时涉及创建指向指针变量的指针。另外：如果您只交换内容，您也可以省略 ->next 指针，而是使用数组，然后交换数组的内容。

恕我直言，对链表进行排序的自然方式是合并排序。下面的片段将列表分为两部分：已经到位的节点和尚未到位的节点。对第二个列表进行排序，并将两个列表合并。拆分和合并都涉及一些指针到指针变量。

#include <stdio.h>
#include <string.h>

struct llist {
        struct llist *next;
        char *payload;
        };

int llist_cmp(struct llist *l, struct llist *r);
struct llist * llist_split(struct llist **hnd
                        , int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_merge(struct llist *one, struct llist *two
                        , int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_sort(struct llist *ptr
                        , int (*cmp)(struct llist *l, struct llist *r) );

struct llist * llist_split(struct llist **hnd, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *this, *save, **tail;

for (save=NULL, tail = &save; this = *hnd; ) {
        if (! this->next) break;
        if ( cmp( this, this->next) <= 0) { hnd = &this->next; continue; }
        *tail = this->next;
        this->next = this->next->next;
        tail = &(*tail)->next;
        *tail = NULL;
        }
return save;
}

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}

struct llist * llist_sort(struct llist *ptr, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *save;

  save=llist_split(&ptr, cmp);
  if (!save) return ptr;

  save = llist_sort(save, cmp);

  return llist_merge(ptr, save, cmp);
}

int llist_cmp(struct llist *l, struct llist *r)
  {
  if (!l) return 1;
  if (!r) return -1;
  return strcmp(l->payload,r->payload);
  }


struct llist lists[] =
{{ lists+1, "one" }
,{ lists+2, "two" }
,{ lists+3, "three" }
,{ lists+4, "four" }
,{ lists+5, "five" }
,{ lists+6, "six" }
,{ lists+7, "seven" }
,{ lists+8, "eight" }
,{ NULL, "nine" }
        };

int main()
{
struct llist *root,*tmp;

root = lists;

fprintf(stdout, "## %s\n", "initial:" );
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%s\n", tmp->payload);
        }

fprintf(stdout, "## %s\n", "sorting..." );
root = llist_sort(root, llist_cmp);

for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%s\n", tmp->payload);
        }
fprintf(stdout, "## %s\n", "done." );

return 0;
}

结果：

## initial:
one
two
three
four
five
six
seven
eight
nine
## sorting...
eight
five
four
nine
one
seven
six
three
two
## done.

Answer 2

对链表进行排序的正确方法是第二种。这也是有道理的，因为您通常希望根据某些属性对对象进行排序，同时保留其其他属性值。在这种情况下，第一种方法并没有多大帮助。

这个想法类似于传统的排序方法。例如，您可以通过迭代元素然后将下一个元素插入到正确排序的链表中的正确位置直到该元素来使用插入排序。有关 C 语言的详细代码，您可以在此处查看维基百科页面。