首页 > 代码库 > Leetcode-Sort List
Leetcode-Sort List
Sort a linked list in O(n log n) time using constant space complexity.
Analsys:
We use Merge Sort.
NOTE: We should practice other sort algorithm, linke Quick Sort and Heap Sort!
Solution:
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 (head==null || head.next==null) return head;15 16 head = sortListRecur(head);17 return head;18 }19 20 public ListNode sortListRecur(ListNode head){21 int len = 1;22 ListNode curNode = head;23 while (curNode.next!=null){24 curNode = curNode.next;25 len++;26 }27 28 if (len==1) return head;29 ListNode leftHead = head;30 ListNode rightHead = null;31 curNode = head;32 for (int i=1;i<len/2;i++){33 curNode = curNode.next;34 }35 rightHead = curNode.next;36 curNode.next = null;37 38 leftHead = sortListRecur(leftHead);39 rightHead = sortListRecur(rightHead);40 41 ListNode preHead = new ListNode(0);42 ListNode end = preHead;43 while (leftHead!=null || rightHead!=null){44 if (leftHead==null){45 end.next = rightHead;46 break;47 }48 49 if (rightHead==null){50 end.next = leftHead;51 break;52 }53 54 if (leftHead.val<rightHead.val){55 end.next = leftHead;56 leftHead = leftHead.next;57 end = end.next;58 } else {59 end.next = rightHead;60 rightHead = rightHead.next;61 end = end.next;62 }63 }64 65 return preHead.next;66 }67 68 }
Leetcode-Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。