当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

leetcode: sort list

发表于: 2014-02-02   作者:michelle_0916   来源:转载   浏览:
摘要: Sort a linked list in O(n log n) time using constant space complexity. ====analysis======= mergeSort for singly-linked list  ====code=======   /** * Definition for sin

Sort a linked list in O(n log n) time using constant space complexity.

====analysis=======

mergeSort for singly-linked list 

====code=======

 
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeSort(ListNode *head, ListNode *newhead) {
if(!head) return newhead;
if(!newhead) return head;

ListNode *smaller = head->val <= newhead->val ? head : newhead;
ListNode *larger = head->val > newhead->val ? head : newhead;
ListNode *result = smaller;

while(smaller->next && larger) {
if(smaller->val <= larger->val && larger->val < smaller->next->val) {

ListNode *q = larger->next;
larger->next = smaller->next;
smaller->next = larger;

smaller = smaller->next;
larger = q;
} else {
smaller = smaller->next;
}
}

if(larger) {
smaller->next = larger;
}

return result;
}
ListNode *sortList(ListNode *head) {
if(!head || !head->next) return head;
ListNode *slow = head;
ListNode *fast = head->next;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

ListNode *rightP = slow->next;
slow->next = NULL;
head = sortList(head);
rightP = sortList(rightP);

return mergeSort(head, rightP);
}
};

 

leetcode: sort list

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

推荐文章
编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号