ChristmasError-Blog

leetcode刷题笔记：144排序链表——归并排序

leetcode刷题笔记
字数统计: 248阅读时长: 1 min
2018/10/10 Share

题目

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

为了完成时间复杂度的要求，使用归并排序是一个很好的技巧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 *     p1 p2
 * };
 */
class Solution {
public:
    ListNode* megresortList(ListNode* left,ListNode *right)
    {
        if(left==NULL) return right;
        if(right==NULL) return left;
        if(left->val <= right->val){
            left->next=megresortList(left->next,right);
            return left;
        }
        else{
            right->next=megresortList(right->next,left);
            return right;
        }
    }
    ListNode* sortList(ListNode* head) 
    {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode* p1=head;
        ListNode* p2=head->next;
        while(p2!=NULL)
        {
            p2=p2->next;
            if(p2==NULL)
                break;
            p2=p2->next;
            p1=p1->next;
        }
        p2=p1->next;
        p1->next=NULL;
        p1=head;
        p1=sortList(p1);
        p2=sortList(p2);
        p1=megresortList(p1,p2);
        return p1;
    }
};
CATALOG
  1. 1. 题目
Total : 16
2018
C++ 数据结构 BST Lambda表达式 Lambda函数 C++ 数据结构 广义表 指针，const C++ 红黑树 数据结构 RBTree hash_map 哈希表 这是建立个人Blog来的第一篇测试博客 RAII 智能指针 很基础的Markdown语法及其效果演示 《深入了解计算机系统》 leetcode刷题笔记 STL学习笔记