首页 > 编程语言 > 详细

3 排序链表(148)

时间:2020-09-04 17:01:48      阅读:78      评论:0      收藏:0      [点我收藏+]

作者: Turbo时间限制: 1S章节: DS:数组和链表

晚于: 2020-07-08 12:00:00后提交分数乘系数50%

截止日期: 2020-07-15 12:00:00

问题描述 :

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

 

示例 1:

输入: 4->2->1->3

输出: 1->2->3->4

 

示例 2:

输入: -1->5->3->4->0

输出: -1->0->3->4->5

 

可使用以下代码,完成其中的sortList函数,其中形参head指向无头结点单链表。

#include<iostream>

using namespace std;

 

struct ListNode

{

    int val;

    ListNode *next;

    ListNode() : val(0), next(NULL) {}

    ListNode(int x) : val(x), next(NULL) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}

};

 

class Solution {

public:

    ListNode* sortList(ListNode* head)

    {

          //填充本函数完成功能

    }

};

 

ListNode *createByTail()

{

    ListNode *head;

    ListNode *p1,*p2;

    int n=0,num;

    int len;

    cin>>len;

    head=NULL;

    while(n<len && cin>>num)

    {

        p1=new ListNode(num);

        n=n+1;

        if(n==1)

            head=p1;

        else

            p2->next=p1;

        p2=p1;

    }

    return head;

}

 

void  displayLink(ListNode *head)

{

    ListNode *p;

    p=head;

    cout<<"head-->";

    while(p!= NULL)

    {

        cout<<p->val<<"-->";

        p=p->next;

    }

    cout<<"tail\n";

}

int main()

{

    ListNode* head = createByTail();

    head=Solution().sortList(head);

    displayLink(head);

    return 0;

}

输入说明 :

首先输入链表长度len,然后输入len个整数,以空格分隔。

输出说明 :

输出格式见范例

输入范例 :

5
-1 5 3 4 0

输出范例:

head-->-1-->0-->3-->4-->5-->tail
#include<iostream>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(NULL) {}
    ListNode(int x) : val(x), next(NULL) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode newhead(-1);
        newhead.next = head;
         ListNode *p = head;
        int length = 0;
        while (p) {
            ++length;
            p = p->next;
        }
        
        for (int step = 1; step < length;step<<= 1) {
            ListNode *cur =  newhead.next;
            ListNode *tail = & newhead;
            
            while (cur) {
                ListNode *left = cur;
                ListNode *right = cut(left, step); 
                cur = cut(right, step); 
                
                tail->next = merge(left, right);
                while (tail->next) {
                    tail = tail->next;
                }
            }
        }
        return  newhead.next;
    }
    
    ListNode* cut(ListNode* head, int n) {
        ListNode *p = head;
        while (--n && p) {
            p = p->next;
        }
        
        if (!p) return NULL;
        
        ListNode *next = p->next;
        p->next = NULL;
        return next;
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode  newhead(-1);
        ListNode *p = & newhead;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                p = l1;
                l1 = l1->next;       
            } else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        p->next = l1 ? l1 : l2;
        return  newhead.next;
    }
};


ListNode *createByTail()
{
    ListNode *head;
    ListNode *p1,*p2;
    int n=0,num;
    int len;
    cin>>len;
    head=NULL;
    while(n<len && cin>>num)
    {
        p1=new ListNode(num);
        n=n+1;
        if(n==1)
            head=p1;
        else
            p2->next=p1;
        p2=p1;
    }
    return head;
}

void  displayLink(ListNode *head)
{
    ListNode *p;
    p=head;
    cout<<"head-->";
    while(p!= NULL)
    {
        cout<<p->val<<"-->";
        p=p->next;
    }
    cout<<"tail\n";
}
int main()
{
    ListNode* head = createByTail();
    head=Solution().sortList(head);
    displayLink(head);
    return 0;
}

 

3 排序链表(148)

原文:https://www.cnblogs.com/zmmm/p/13614695.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!