首页 > 代码库 > 【Leetcode】Sort List JAVA实现
【Leetcode】Sort List JAVA实现
Sort a linked list in O(n log n) time using constant space complexity.
1、分析
该题主要考查了链接上的合并排序算法。
2、正确代码实现
package com.edu.leetcode;import com.edu.leetcode.ListNode;public class SortList { /** * @param args */ public ListNode Merge(ListNode first,ListNode second){ //合并两个有序链表，并返回新链表的投结点 ListNode rear; ListNode head; rear=head=new ListNode(-1); while(first!=null&&second!=null){ if(first.val<=second.val){ rear.next=first; rear=first; first=first.next; } else{ rear.next=second; rear=second; second=second.next; } } if(first!=null) rear.next=first; else rear.next=second; return head.next; } public ListNode sortList(ListNode head){ /* * 实现链表的合并排序：1、将链表划分成基本相等的两个链表 * 2、递归将这两个链接继续划分，直到链表的长度为0或者1为止 * 3、调用Merge（）将链接进行合并 */ if(head==null||head.next==null) return head; ListNode mid =head; ListNode pos =mid.next; while(pos!=null){ pos=pos.next; if(pos!=null){ pos=pos.next; mid=mid.next; } } ListNode q=sortList(mid.next); mid.next=null; return Merge(sortList(head), q); } public static void main(String[] args) { // TODO Auto-generated method stub ListNode first1 = new ListNode(0); ListNode rear1 =first1; for(int i=9;i>=1;i--){ ListNode q= new ListNode(i); rear1.next=q; rear1=q; } ListNode q=first1; while(q!=null){ System.out.print(q.val+ ","); q=q.next; } System.out.println(); SortList sl = new SortList(); sl.sortList(first1); ListNode p=first1; while(p!=null){ System.out.print(p.val+ ","); p=p.next; } System.out.println(); }}
3、有点问题的代码
这里的问题主要是将上面的SortList（）方法分成两步实现：Divide()和MergeSort（）两部分。个人觉得应该是一样的。但运行结果确实不同，如果大神浏览，请指点一下小弟。。
class ListNode{ int val; ListNode next=null; public ListNode(){ } public ListNode(int val){ this.val=val; }}public class SortList { public ListNode Merge(ListNode first,ListNode second){ ListNode rear; ListNode head; rear=head=new ListNode(); while(first!=null&&second!=null){ if(first.val<=second.val){ rear.next=first; rear=first; first=first.next; } else{ rear.next=second; rear=second; second=second.next; } } if(first!=null) rear.next=first; else rear.next=second; return head.next; } public ListNode Divide(ListNode first){ //将一个链表划分成两个基本相等的子链表 if(first==null) return null; ListNode mid =first; ListNode pos =mid.next; while(pos!=null){ pos=pos.next; if(pos!=null){ pos=pos.next; mid=mid.next; } } ListNode q=mid.next; mid.next=null; return q; } public void MergeSort(ListNode first){ //合并排序 if(first!=null&&first.next!=null){ ListNode second =Divide(first); //将链表划分成两部分 MergeSort(first); //递归 MergeSort(second); Merge(first, second); } } public static void main(String[] args) { // TODO Auto-generated method stub ListNode first1 = new ListNode(0); ListNode rear1 =first1; for(int i=9;i>=1;i--){ ListNode q= new ListNode(i); rear1.next=q; rear1=q; } ListNode q=first1; while(q!=null){ System.out.print(q.val+ ","); q=q.next; } System.out.println(); SortList sl = new SortList(); sl.MergeSort(first1); ListNode p=first1; while(p!=null){ System.out.print(p.val+ ","); p=p.next; } System.out.println(); }}
【Leetcode】Sort List JAVA实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。