1.题目描述：
2.解题思路：
本题是要堆一个链表进行排序，并且要求时间复杂度为 O(n log n)。很明显，要用到分治的思想，用二分法进行归并排序：找到链表的middle节点，然后递归对前半部分和后半部分分别进行归并排序，最后对两个已排好序的链表进行Merge。
分为三步：
（1）找到中间结点，将链表分割成两部分。这里用到快慢两个指针的方法。
（2）对前后每一部分分别进行归并排序。这里用到递归。
（3）对两个已排好序的链表进行合并。这里用到前面merge 2 list的方法。
3.Java代码：
//public class LeetCode148 为测试代码 public class LeetCode148 { public static void main(String[] args) { ListNode n1=new ListNode(3),n2=new ListNode(2),n3=new ListNode(1),n4=new ListNode(5); ListNode p=n1; n1.next=n2; n2.next=n3; n3.next=n4; System.out.print("初始时链表："+p.val); while(p.next!=null){ System.out.print("->"+p.next.val); p=p.next; } System.out.println(); ListNode head=new Solution().sortList(n1); System.out.print("排序后链表："+head.val); while(head.next!=null){ System.out.print("->"+head.next.val); head=head.next; } } } //class Solution为ac代码 class Solution { public ListNode sortList(ListNode head) { if(head==null||head.next==null) return head; // step 1. 将链表分割为两部分 ListNode pre=null,slow=head,fast=head; while(fast!=null&&fast.next!=null){ pre=slow;//pre指针是为了记住slow的前一个节点位置 slow=slow.next; fast=fast.next.next; } pre.next=null;//将链表从pre和slow之间断开 // step 2. 对每一部分进行排序 ListNode l1=sortList(head); ListNode l2=sortList(slow); // step 3. merge l1 and l2 return merge2Lists(l1,l2); } private ListNode merge2Lists(ListNode l1, ListNode l2) { ListNode fakeHead=new ListNode(0); ListNode p=fakeHead; while(l1!=null&&l2!=null){ if(l1.val<l2.val){ p.next=l1; l1=l1.next; }else{ p.next=l2; l2=l2.next; } p=p.next; } if(l1!=null) p.next=l1; if(l2!=null) p.next=l2; return fakeHead.next; } } class ListNode{ int val; ListNode next; ListNode(int x) { val = x; } }
测试结果：
思考：我将merge2Lists方法写成递归的写法时，即
1 private ListNode merge2Lists(ListNode l1, ListNode l2) { 2 if(l1==null) return l2; 3 if(l2==null) return l1; 4 if(l1.val<l2.val){ 5 l1.next=merge2Lists(l1.next, l2); 6 return l1; 7 }else{ 8 l2.next=merge2Lists(l1, l2.next); 9 return l2; 10 } 11 }
这时在eclipse上测试完全没问题，但是在LeetCode上提交不通过，至今没想明白说明问题，如果哪位大神明白为什么，一定告诉我。。。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
