建设网站需要多少钱济南兴田德润o厉害吗,广州seo网站推广,网站优化助手,建立百度网站【题干】
给你链表的头结点 head #xff0c;请将其按 升序 排列并返回 排序后的链表 。
【思路】
递归版归并法链表版#xff5e;没什么特别好说的#xff08;非递归版归并也是可以哒#xff0c;但是马上要考试了今天懒得写了#xff01;打个flag在这里也许哪天想起来…【题干】
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
【思路】
递归版归并法链表版没什么特别好说的非递归版归并也是可以哒但是马上要考试了今天懒得写了打个flag在这里也许哪天想起来会补写一下首先是分割这一步在链表里会麻烦一点因为要找到链表的中点得用快慢指针快指针每次移动 2 步慢指针每次移动 1步当快指针到达链表末尾时慢指针指向链表的中点。对拆出的两个子链表递归的进行拆分直到达到递归出口只有一个节点逐层归并有序的子链表done。 【题解】
class Solution {
public:ListNode* sortList(ListNode* head) {return sortList(head, nullptr);}ListNode* sortList(ListNode* head, ListNode* tail) {if (head nullptr) {return head;}if (head-next tail) {head-next nullptr;return head;}ListNode* slow head, *fast head;while (fast ! tail) {slow slow-next;fast fast-next;if (fast ! tail) {fast fast-next;}}ListNode* mid slow;return merge(sortList(head, mid), sortList(mid, tail));}ListNode* merge(ListNode* head1, ListNode* head2) {ListNode* dummyHead new ListNode(0);ListNode* temp dummyHead, *temp1 head1, *temp2 head2;while (temp1 ! nullptr temp2 ! nullptr) {if (temp1-val temp2-val) {temp-next temp1;temp1 temp1-next;} else {temp-next temp2;temp2 temp2-next;}temp temp-next;}if (temp1 ! nullptr) {temp-next temp1;} else if (temp2 ! nullptr) {temp-next temp2;}return dummyHead-next;}
};
