[数据结构与算法]BM12 单链表的排序

描述

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：0 < n \le 1000000<n≤100000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

示例1

输入：

[1,3,2,4,5]

返回值：

{1,2,3,4,5}

示例2

输入：

[-1,0,-2]
返回值：

{-2,-1,0}

方法一.

归并排序

代码：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */

struct ListNode* sortInList(struct ListNode* head ) {
    if(head==NULL||head->next==NULL){
         return head;
    }
    struct ListNode*fast=head->next;
    struct ListNode* slow=head;
    while(fast!=NULL&&fast->next!=NULL){
        fast=fast->next->next;
        slow=slow->next;
    }
    
    struct ListNode *right=slow->next;  //右边第一个节点
    struct ListNode* le=NULL;
    struct ListNode* re=NULL;
    slow->next=NULL ; //断开形成两个链表
    
    //左右两边归并
    le=sortInList(head);   
    re=sortInList(right);
    
    //创建新的带头结点链表
    struct ListNode*  pp=(struct ListNode*)malloc(sizeof(struct ListNode)*1);
    struct ListNode* cur=pp;
    while(le!=NULL&&re!=NULL){
        if(le->val<re->val){
            cur->next=le;
            le=le->next;
        }
        else{
            cur->next=re;
            re=re->next;
        }
        cur=cur->next;
        cur->next=NULL;
    }
    //cur->next=(le!=NULL)?le:re;
    if(le!=NULL){
        cur->next=le;
    }
   if(re!=NULL){
        cur->next=re;
    }
    return pp->next;
}


//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=
/*
或者：
struct ListNode* merge(struct ListNode* p,struct ListNode*q){
    struct ListNode*cur=malloc(0);
    struct ListNode*head=cur;
    while(p&&q){
        if(p->val<q->val){
            cur->next=p;
            p=p->next;
        }
        else{
            cur->next=q;
            q=q->next;
        }
        cur=cur->next;
    }
     // 最后添加未对比的链表部分判断左链表是否为空
    cur->next=p?p:q;
    return head->next;
}

struct ListNode*  mer(struct ListNode *p){
        if(p==NULL||p->next==NULL){
                return p;
        }
    
        struct ListNode*slow=p;
        struct ListNode*fast=p->next;
        while(fast&&fast->next){   //分治
            slow=slow->next;
            fast=fast->next->next;
        }
        struct ListNode* r=slow->next;  //右边的起点
        slow->next=NULL;   //左边以中心点断开，slow为断开点
    
        struct ListNode*left=mer(p);
        struct ListNode* right=mer(r);
    
        struct ListNode*cur= (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode*head=cur;
        while(left&&right){
            if(left->val<right->val){
                cur->next=left;
                left=left->next;
            }
            else{
                cur->next=right;
                right=right->next;
            }
            cur=cur->next;
        }
         // 最后添加未对比的链表部分判断左链表是否为空
        cur->next=left?left:right;
        return head->next;
}
 struct ListNode* sortInList(struct ListNode* head ) {
      if(head==NULL||head->next==NULL){
          return head;
      }
      return mer(head);
}
*/

方法二

暴力循环java

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        ListNode left=head;
        while(left!=null){
            ListNode temp=left.next;
            while(temp!=null){
                if(temp.val<left.val){
                    int t=left.val;
                    left.val=temp.val;
                    temp.val=t;
                }
                temp=temp.next;
            }
            left=left.next;  
        }
        return head;
    }
}