> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/5.linkedlist/98sort-list.md).

# 148.Sort List (M)

https\://leetcode.com/problems/sort-list/

## 1.Description(Medium)

Sort a linked list in O(*n\_log\_n*) time using constant space complexity.

**Example**

Given`1->3->2->null`, sort it to`1->2->3->null`.

## 2.Code

排序要求O(nlogn)的时间,就是Quicksort, Mergesort, Heapsort

没有n次new语句的就是constant space.

Merge Sort：

1> 找中点 middle,断开前后两个链表

2> Recursive (Divided left right)

3> Merge (left,right)

```
public ListNode sortList(ListNode head){
           if(head==null || head.next==null){
               return head;
           }

           ListNode middle=findMiddle(head);
           ListNode right=sortList(middle.next);
           middle.next=null;
           ListNode left=sortList(head);

           return merge(left,right);

   }

   public ListNode findMiddle(ListNode head){
           if(head==null){
               return null;
           }
           ListNode slow=head;
           ListNode fast=head.next;
           while(fast!=null && fast.next!=null){
               fast=fast.next.next;
               slow=slow.next;
           }
           return slow;
   }

   public ListNode merge(ListNode left,ListNode right){
           ListNode dummy=new ListNode(0);
           ListNode temp=dummy;

           while(left!=null && right!=null){
               if(left.val<right.val){
                   temp.next=left;
                   left=left.next;
               }else{
                   temp.next=right;
                   right=right.next;
               }
               temp=temp.next; //caution
           }
           if(left!=null){
               temp.next=left;
           }
           if(right!=null){
               temp.next=right;
           }
           return dummy.next;
   }
```