首页 > 代码库 > Sort List

Sort List

2024-08-07 23:21:37   219人阅读

Sort List 

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

这道题我想过用直接插入，超时了。百度了一下，用的是归并排序，排序以前用的都是数组，这次用链表，不太习惯

参考：http://blog.csdn.net/worldwindjp/article/details/18986737

 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(null == head || null == head.next)15             return head;                                        //空链表和只有一个节点的链表直接返回head16         17         ListNode middle = getMiddle(head);                        //得到中点节点18         ListNode next = middle.next;19         middle.next = null;          20         21         return merge(sortList(head), sortList(next));22     }23     24     /**25      * 获取链表的中间位置节点，一个指针走一步，另一个指针走两步26      * @param head27      * @return28      */29     public ListNode getMiddle(ListNode head){30         ListNode fast = head;31         ListNode slow = head;32         33         while(null != fast.next && null != fast.next.next){34             fast = fast.next.next;35             slow = slow.next;36         }37         38         return slow;39     }40     41     /**42      * 合并两个有序链表43      * @param a44      * @param b45      */46     public ListNode merge(ListNode a, ListNode b){47         ListNode dummyHead = new ListNode(Integer.MIN_VALUE);48         ListNode cur = dummyHead;49         while(null != a && null != b){            //开始合并两个链表，放到dummyHead为头结点的链表中50             if(a.val <= b.val){51                 cur.next = a;52                 a = a.next;53             }54             else{55                 cur.next = b;56                 b = b.next;57             }58             cur = cur.next;59         }//while60         cur.next = a != null ? a : b;61         62         return dummyHead.next;63     }64 }

 

Sort List


联系
我们