首页 > 代码库 > LeetCode-Sort List[AC源码]
LeetCode-Sort List[AC源码]
package com.lw.leet4;/** * @ClassName:Solution * @Description: * Sort List * Sort a linked list in O(n log n) time using constant space complexity. * @Author LiuWei * @Date 2014年8月18日上午10:17:45 * @Mail nashiyue1314@163.com *//** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode getMiddleNode(ListNode head){ ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } public ListNode mergeList(ListNode list1,ListNode list2){ ListNode newHead = new ListNode(-1); ListNode curNode = newHead; while(list1 != null && list2 != null){ if(list1.val<= list2.val){ curNode.next = list1; list1 = list1.next; } else{ curNode.next = list2; list2 = list2.next; } curNode = curNode.next; } if(list1 == null){ curNode.next = list2; } else{ curNode.next = list1; } return newHead.next; } public ListNode sortList(ListNode head) { if(head == null || head.next == null){ return head; } ListNode middleNode = getMiddleNode(head); ListNode nextNode = middleNode.next; middleNode.next = null; return mergeList(sortList(head), sortList(nextNode)); } public static void main(String[] args){ int[] arr = {4,19,14,5,-3,1,8,5,11,15}; ListNode head = new ListNode(arr[0]); ListNode curr = head; for(int i=1; i<arr.length; i++){ ListNode node = new ListNode(arr[i]); curr.next = node; curr = curr.next; } ListNode tmp = new Solution().sortList(head); while(tmp != null){ System.out.println(tmp.val); tmp = tmp.next; } }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。