花了一晚上都没整明白,细节太重要啦!!!
里面的几个步骤都是难点:
1.自底向上思想;
2.断链
3.归并
4.合链
涉及到的指针操作&&边界条件多,一不小心就入坑了。。。
不过归根结底,还是自己太菜啊。。
呜呜
// // Created by jt on 2020/8/8. // 循环实现:不会超时 // /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode *sortList(ListNode *head) { // write code here // 要点:bottom-to-up;断链操作;合并操作(重新链接) if (!head || !head->next) { return head; } ListNode dummy(0); dummy.next = head; auto p = head; // 开始bottom-to-up int size = 1; while (p->next) { ++size; p = p->next; } for (int step = 1; step < size; step <<= 1) { auto curHead = dummy.next; auto tail = &dummy; while (curHead) { auto left = curHead; auto right = cut(left, step); // left->@->@ right->@->@->@... curHead = cut(right, step); // left->@->@ right->@->@ curHead->@->... tail->next = merge(left, right); while (tail->next) { tail = tail->next; } } } return dummy.next; } ListNode* cut(ListNode *left, int step) { ListNode *p = left; // 找到左链最后一个节点 while (--step && p) { p = p->next; } // 如果左链节点数不够 if (!p) return nullptr; auto next = p->next; p->next = nullptr; // 断链 return next; } ListNode *merge(ListNode *left, ListNode *right) { ListNode dummy(0); ListNode *head = &dummy; while (left && right) { if (left->val > right->val) { head->next = right; head = right; right = right->next; } else { head->next = left; head = left; left = left->next; } } head->next = left ? left : right; return dummy.next; } };