当我被告知"Sort a singly linked list"时会发生什么

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

链表背后的全部思想是，可以在不影响内容的情况下更改链接。更改指针有时涉及创建指向指针变量的指针。此外：如果您只交换内容，您还可以省去->下一个指针，使用数组，并交换数组的内容。

IMHO对链表进行排序的自然方式是合并排序。下面的片段将列表分为两部分：已经到位的节点和没有到位的节点。对第二个列表进行排序，并将这两个列表合并。两个拆分&合并涉及一些指针到指针的变量。

#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, "## %sn", "initial:" );
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%sn", tmp->payload);
        }
fprintf(stdout, "## %sn", "sorting..." );
root = llist_sort(root, llist_cmp);
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%sn", tmp->payload);
        }
fprintf(stdout, "## %sn", "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语言的详细代码，您可以在此处查看维基百科页面。