首页 > 代码库 > 【leetcode刷题笔记】Sort List
【leetcode刷题笔记】Sort List
Sort a linked list in O(n log n) time using constant space complexity.
题解：实现一个链表的归并排序即可。主要分为三部分：
1.找到中点并返回的函数findMiddle;
2.归并函数merge;
3.排序函数sortList。
数组的findMiddle函数非常容易实现，链表就有一点tricky了。首先设置两个指针，一个slow初始化为head，一个fast初始化为head.next，然后slow一次走一步，fast一次走两步，那么当fast达到终点的时候，slow就正好到达中点了。
merge函数很简单，就是每次比较两个链表头结点的大小，把较小的拿过来放在新链表后面。
sortList是一个递归的函数，分别递归的排序[head,mid]和[mid.next,tail]之间的元素，然后把它们归并。
代码如下：
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 private ListNode findMiddle(ListNode head){14 ListNode slow = head;15 ListNode fast = head.next;16 while(fast != null && fast.next != null){17 slow = slow.next;18 fast = fast.next.next;19 }20 return slow;21 }22 private ListNode merge(ListNode head1,ListNode head2){23 if(null == head1)24 return head2;25 if(null == head2)26 return head1;27 ListNode head;28 if(head1.val > head2.val){29 head = head2;30 head2 = head2.next;31 }32 else{33 head = head1;34 head1 = head1.next;35 }36 ListNode tail = head;37 while(head1 != null && head2 != null){38 if(head1.val > head2.val){39 tail.next = head2;40 head2 = head2.next;41 }42 else{43 tail.next = head1;44 head1 = head1.next;45 }46 tail = tail.next;47 }48 if(head1 != null)49 tail.next = head1;50 if(head2 != null)51 tail.next = head2;52 return head;53 }54 public ListNode sortList(ListNode head) {55 if(head == null || head.next == null)56 return head;57 ListNode mid = findMiddle(head);58 ListNode right = sortList(mid.next);59 mid.next = null;60 ListNode left = sortList(head);61 62 return merge(left,right);63 }64 }
在人人上看到一个很好的汇集leetcode答案的网站：http://answer.ninechapter.com/，据说是google和facebook等工程师给出的答案，可以学习一下。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。