首页 > 代码库 > LeetCode Solutions : Sort List

LeetCode Solutions : Sort List

2024-08-03 01:10:39   210人阅读

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

O(n log n)，我们可以第一时间想到常用的二路归并排序，快速排序和堆排序，其中快排和堆排只适用于线性表，即数组，故这道编程题毫无疑问用二路归并排序；

 * 1. 利用一个小技巧，可以设置慢行指针low和快行指针fast，把链表分成两部分来操作，即first和second链表
 * 2. 递归排序first和second链表，即

first=sortList(head);
second=sortList(second);
 * 3. 合并这两个链表，即：mergeListSort(first,second)

【代码实现

[java] view plaincopyprint?
    1. /** 
    2.  * Definition for singly-linked list. 
    3.  * class ListNode { 
    4.  *     int val; 
    5.  *     ListNode next; 
    6.  *     ListNode(int x) { 
    7.  *         val = x; 
    8.  *         next = null; 
    9.  *     } 
    10.  * } 
    11.  */  
    12. public class Solution {  
    13.     public ListNode sortList(ListNode head) {  
    14.         if(head==null||head.next==null)  
    15.             return head;  
    16.         ListNode fast=head;  
    17.         ListNode slow=head;  
    18.         while(fast.next!=null&&fast.next.next != null){  
    19.             fast=fast.next.next;  
    20.             slow=slow.next;  
    21.         }  
    22.         ListNode second=slow.next;  
    23.         slow.next=null;  
    24.         ListNode first=sortList(head);  
    25.         second=sortList(second);  
    26.         return mergeListSort(first,second);  
    27.     }  
    28.     private ListNode mergeListSort(ListNode first,ListNode second){  
    29.         ListNode newList=new ListNode(0);  
    30.         ListNode p=newList;  
    31.         while(first!=null&&second!=null){  
    32.             if(first.val<=second.val){  
    33.                 p.next=first;  
    34.                 first=first.next;  
    35.             }else{  
    36.                 p.next=second;  
    37.                 second=second.next;  
    38.             }  
    39.             p=p.next;  
    40.         }  
    41.         if(first!=null)  
    42.             p.next=first;  
    43.         if(second!=null)  
    44.             p.next=second;  
    45.         return newList.next;  
    46.     }     
    47. } 

LeetCode Solutions : Sort List


联系
我们