算法札记——5.14

今天记录一道有难度的链表题——148. 排序链表 - 力扣LeetCode题目要求是让我们对一个链表进行排序首先可以想到的最简单的思路就是将所有的节点存储到一个数组然后数组以node-val排序最后遍历数组连接各节点即可。以下是相关实现/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { if (head nullptr) return nullptr; ListNode* cur head; vectorListNode* tmp; while (cur) { tmp.push_back(cur); cur cur-next; } sort(tmp.begin(), tmp.end(), [](const ListNode* n1, const ListNode* n2){ return n1-val n2-val; }); for (int i 1; i tmp.size(); i) { ListNode* prev tmp[i - 1]; prev-next tmp[i]; } tmp.back()-next nullptr; return tmp[0]; } };但题目中存在一个进阶要求需要空间复杂度为O(1)这便是该题的难点。可以说若使用之前的解法仅能算简单题但要求却可让该题进化到困难题。但还是有思路的可以借鉴归并排序的思想和另一道简单的算法题的思路——21. 合并两个有序链表 - 力扣LeetCode该简单题的解法/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode head(-1); ListNode* phead head; ListNode* prev phead, *l1 list1, *l2 list2; while (l1 l2) { if (l1-val l2-val) { prev-next l1; l1 l1-next; } else { prev-next l2; l2 l2-next; } prev prev-next; } prev-next l1 nullptr ? l2 : l1; return phead-next; } };可是鉴于空间复杂度仅能为O(1)显然不能仿照归并排序创建一个tmp的拷贝数组的。但参照上述的简单题我们可以使用指针指向来划分区间进行归并。而且本题无法使用递归版本的归并因为递归涉及到函数栈帧的开辟也会产生O(logN)的空间复杂度此处应使用迭代版本归并排序。对于归并排序的递归与非递归的思路与实现可跳转博主这篇博文 八大排序算法C实现-CSDN博客 的归并排序篇。以下是具体实现本人水平较菜所以使用的变量有点多/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { ListNode* MergeSortListNonR(ListNode* head, int n) { int gap 1; ListNode t(-1, head); ListNode* phead t; while (gap n) { ListNode* prev phead; for (int i 0; i n; i 2 * gap) { int begin i, end min(i 2 * gap, n) - 1; int left1 begin, right1 begin gap - 1; int left2 begin gap, right2 end; if (right2 left2) break; ListNode* l1 prev-next, *l2 l1, *tail1 nullptr; for (int i left1; i right1; i) { tail1 l2; if (l2 nullptr) cout gap endl; l2 l2-next; } ListNode* tail2 l2; for (int j left2; j right2; j) tail2 tail2-next; ListNode* tail tail2-next; while (left1 right1 left2 right2) { if (l1-val l2-val) { prev-next l1; left1; l1 l1-next; } else { prev-next l2; left2; l2 l2-next; } prev prev-next; } if (left1 right1) { prev-next l1; //让prev指向区间尾部 prev tail1; } if (left2 right2) { prev-next l2; //让prev指向区间尾部 prev tail2; } prev-next tail; } gap * 2; } return phead-next; } public: ListNode* sortList(ListNode* head) { int n 0; ListNode* cur head; while (cur) { n; cur cur-next; } ListNode* newHead MergeSortListNonR(head, n); return newHead; } };以上实现需要注意的点是prev指针的相关细节每趟归并最后应将prev指向余下left1/left2的区间末尾并且让prev-next指向此趟排序的整个区间右侧外的第一个节点(tail)。