c++ - 使用链表排序插入

Question

我在为链表中的排序插入实现一个迭代函数时遇到了一些困难。我以前用递归完成了这一点，这在insert()调用函数时要容易得多，但在这里我对如何实现(l->data < data)条件有点困惑：

typedef struct E_Type * List;

struct E_Type
{
  int data;
  struct E_Type* next;
};

和功能：

insert(List & l, int data){
  if (l == 0 || l->data > data){
    List new_list = new E_Type;
    new_list->data = data;
    new_list->next = l;
    l = new_list;
  }
  else if (l->data < data){
    List new_list = new E_Type; 
    new_list->data = data;
    new_list->next = l; //i am shooting in the dark with this one
    l = new_list;
  }
}

Answer 1

我不会为你编写代码，但会提供一些提示。

从根本上讲，有两种情况：

1. 被插入的元素成为新的头部。在这种情况下，您需要更新l.
2. 插入的元素不会成为新的头部。在这种情况下，您需要一个循环。

如果我是你，我会先用笔和纸处理这两种情况。