【每日一题】06 排序链表

问题描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

求解

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* sortList(struct ListNode* head) {struct ListNode * p = head;if(p == NULL){return head;}struct ListNode * q = head->next;int t;while(p->next != NULL){while(q !=NULL){//printf("before: p: %d, q: %d\n", p->val, q->val);if(p->val > q->val){t = p->val;p->val = q->val;q->val = t;}//printf("after: p: %d, q: %d\n", p->val, q->val);q = q->next;}p = p->next;//printf("p : %d\n", p->val);q = p->next;//printf("q : %d\n", q->val);}return head;
}

该方法时间复杂度O(n^2)过高

后续补上使用快速排序方法提升时间复杂度