已知线性表存储在带头结点的单链表head中,请设计算法函数void sort(linklist head),将head中的结点按结点值升序排列。
时间: 2023-05-28 22:05:38 浏览: 72
算法思路:
1. 遍历链表,记录链表的长度n。
2. 用插入排序的思想对链表进行排序,排序过程中需要维护一个有序的子链表。
3. 对于链表中的每一个结点,从已排序的子链表的头结点开始,依次比较结点值,找到插入位置,插入到子链表中。
算法实现:
```
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode, *LinkList;
void sort(LinkList head) {
if (head == NULL || head->next == NULL) {
return;
}
int n = 0;
ListNode* p = head->next;
while (p != NULL) {
n++;
p = p->next;
}
for (int i = 1; i < n; i++) {
ListNode* pre = head;
ListNode* cur = pre->next;
for (int j = 0; j < i; j++) {
pre = pre->next;
cur = cur->next;
}
ListNode* p = head->next;
ListNode* q = head;
while (p != cur) {
if (p->val > cur->val) {
pre->next = cur->next;
q->next = cur;
cur->next = p;
break;
}
p = p->next;
q = q->next;
}
}
}
```
算法分析:
时间复杂度:O(n^2),其中n为链表的长度,因为要遍历链表n次,每次遍历需要比较i次,i的取值范围是1到n-1。
空间复杂度:O(1),只需要维护少量的指针变量。