给定一个具有n个元素的顺序表，建立一个有序线性链表的时间复杂度为 ()。

建立有序链表的时间复杂度为O(n^2)，具体过程如下：

1.先将第一个元素作为有序链表的第一个结点；

2.依次将剩余的元素插入到有序链表中：

- 从有序链表的头结点开始，逐个比较元素大小，找到第一个比当前元素大的结点；
- 将当前元素插入到该结点的前面。

由于需要逐个比较并插入元素，所以时间复杂度为O(n^2)。

相关问题

给定一个只包含数字的有序单向链表，设计算法求链表中位数

给定一个只包含数字的有序单向链表，求链表的中位数可以分为两个情况：链表长度为奇数和偶数。

1. **当链表长度为奇数**：
- 中位数就是中间的那个元素，你可以遍历链表，找到中间位置（即链表长度除以 2 的整数部分），这个位置上的节点即为中位数。

2. **当链表长度为偶数**：
- 中位数则是两个中间值的平均值。首先找到链表长度的一半，然后分别访问位于这两个位置的节点，取它们的平均值作为中位数。

以下是算法的一个基本流程：

- 初始化两个指针 `slow` 和 `fast`，都指向链表头。
- 使用快慢指针法找到链表的中间位置：`fast` 指针每次前进两步，`slow` 指针每次前进一步，直到 `fast` 到达链表尾部（此时 `fast` 指针会落在 `slow` 的前一个位置）。
- 如果链表长度为偶数，那么 `slow` 就在中间位置；如果为奇数，则再让 `slow` 向前移动一位。
- 返回 `slow` 指针所指的节点的数值。

下面是Python代码示例：

def findMedianSortedList(head):
    slow, fast = head, head
    if head is not None:
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

    # 如果链表长度为奇数
    if fast is None or fast.next is None:
        return slow.value
    # 如果链表长度为偶数
    else:
        mid = slow.next
        return (slow.value + mid.value) / 2

给定一个只包含数字的有序单向链表，设计C算法求链表中位数

为了在C语言中找到一个仅包含数字的有序单向链表的中位数，我们可以使用分治法的思想。由于链表已经排序，我们不需要遍历整个链表。如果链表长度是奇数，那么中位数就是中间那个元素；如果是偶数，中位数则是中间两个元素的平均值。

以下是简化的算法步骤：

1. 定义两个指针，快指针（p1）初始指向链表头，慢指针（p2）初始位置比快指针慢一步。
2. 快指针每次移动两步，直到到达链表的末尾。这样当快指针到了链表尾部时，慢指针会恰好位于中间位置（对于奇数个节点），或前一个中间位置（对于偶数个节点）。
3. 当快指针到达链表尾部时，检查慢指针的位置：
- 如果链表长度是奇数，返回慢指针所指向的节点。
- 如果链表长度是偶数，继续将慢指针向前移动一位，然后返回慢指针和下一个节点的平均值。

以下是一个简单的C语言函数实现示例：

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

double findMedianSortedList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head->val; // 链表为空或只有一个元素的情况
    }
    
    ListNode *p1 = head;
    ListNode *p2 = p1->next;
    while (p2->next != NULL) {
        p1 = p1->next;
        p2 = p2->next->next;
    }

    double median;
    if (p1->next == NULL) { // 链表长度为奇数
        median = (double)p1->val;
    } else { // 链表长度为偶数
        median = (double)(p1->val + p2->val) / 2.0;
    }
    return median;
}