首页 > 代码库 > leetcode - [4]Sort List
leetcode - [4]Sort List
Sort a linked list in O(n log n) time using constant space complexity.
思路:采用归并排序或者快速排序
#include <iostream>using namespace std;struct ListNode { int val; ListNode *next; ListNode(int x): val(x), next(NULL) {}};class Solution {public: ListNode *sortList(ListNode *head) { if (!head || head->next == NULL) return head; ListNode *PA = head, *PB = head; while (PA && PB && PB->next && PB->next->next) { PA = PA->next; PB = PB->next->next; } PB = PA->next; PA->next = NULL; PA = head; PA = sortList(PA); PB = sortList(PB); return mergeList(PA, PB); } ListNode *mergeList(ListNode *PA, ListNode *PB) { if (!PB) return PA; if (!PA) return PB; ListNode *merge, *head; if (PA->val < PB->val) { head = PA; PA = PA->next; } else { head = PB; PB = PB->next; } merge = head; while (PA && PB) { if (PA->val < PB->val) { merge->next = PA; PA = PA->next; } else { merge->next = PB; PB = PB->next; } merge = merge->next; } if (PA) merge->next = PA; if (PB) merge->next = PB; return head; }};int main(int argc ,char *argv[]){ ListNode *p, *q; p = new ListNode(3); p->next = new ListNode(2); p->next->next = new ListNode(4); Solution *solution = new Solution(); p = solution->sortList(p); while(p) { cout << p->val << endl; p = p->next; } return 0;}
leetcode - [4]Sort List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。