leetcode 147.对链表进行插入排序

1.题目要求:

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。插入排序 算法的步骤:插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。对链表进行插入排序。

2.题目代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///插入排序函数:void insert_sort(int* arr,int length){for(int i = 1;i < length;i++){if(arr[i - 1] > arr[i]){int temp = arr[i];int j;for(j = i - 1;j >= 0&&temp < arr[j];j--){arr[j + 1] = arr[j];}arr[j + 1] = temp;}}}
struct ListNode* insertionSortList(struct ListNode* head) {int count = 0;struct ListNode* cur = head;//查到结点数目while(cur){count++;cur = cur->next;}//创造数组int* number = (int*)malloc(sizeof(int) * count);int j = 0;cur = head;//把链表的节点存入数组中while(cur){number[j] = cur->val;j++;cur = cur->next;}//进行插入排序insert_sort(number,j);//把排序好的数组存入链表cur = head;j = 0;while(cur){cur->val = number[j];j++;cur = cur->next;}return head;
}