在具有领先节点的单链表中存储了n个记录，设计了一种实现简单选择排序的算法。 要求：(1)给出算法的基本设计思想；(2)根据设计思想，使用C或C++语言对算法进行描述。(3)解释该算法的平均时间复杂度。如果链式存储被顺序存储替换，请解释其时间复杂性。

(1) 该算法的基本设计思想为：每次从未排序的子链表中选择一个最小的节点，将其插入到已排序子链表的末尾，直到所有节点都被排序。

(2) C++代码如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* selectionSort(ListNode* head) {
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *prev = dummy;
    while (prev->next) {
        ListNode *cur = prev->next;
        ListNode *minNode = prev;
        while (cur) {
            if (cur->val < minNode->val)
                minNode = cur;
            cur = cur->next;
        }
        ListNode *tmp = prev->next;
        prev->next = minNode;
        prev = prev->next;
        minNode = minNode->next;
        prev->next = tmp;
    }
    return dummy->next;
}

(3) 该算法的平均时间复杂度为O(n^2)，因为每次需要遍历未排序子链表找到最小的节点。如果链式存储被顺序存储替换，则时间复杂度变为O(nlogn)，因为可以使用快速排序或归并排序等更高效的排序算法。