第（4）题 sort-list 知识点：链表，排序 题述：Sort a linked list in O(n log n) time using constant space complexity. 题意就是要求用一个时间复杂度为O(n log n)的方法对一个链表排序。 思路：要求时间复杂度为O(n log n)，所以要将链表从中一分为二，然后利用归并排序。还需要使用递归。 代码如下：
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode sortList(ListNode head) { int size = 0; ListNode current = head; if( head == null || head.next == null ){ return head; } while( current != null ){ size++; current = current.next; } ListNode mid = head; int size_mid = (size-1)/2; for( int i = 1; i <= size_mid; i++){ mid = mid.next; } ListNode left = mid.next; mid.next = null; ListNode l1 = sortList(head); ListNode l2 = sortList(left); ListNode result = merge(l1,l2); return result; } public ListNode merge(ListNode l1, ListNode l2){ if( l1 == null ){ return l2; } if( l2 == null ){ return l1; } ListNode head,cur,l1_cur=l1,l2_cur=l2; if( l1_cur.val < l2_cur.val ){ head = l1_cur; cur = head; l1_cur = l1_cur.next; }else{ head = l2_cur; cur = head; l2_cur = l2_cur.next; } while( l1_cur != null && l2_cur != null){ if( l1_cur.val < l2_cur.val ){ cur.next = l1_cur; l1_cur = l1_cur.next; }else{ cur.next = l2_cur; l2_cur = l2_cur.next; } cur = cur.next; } if( l1_cur != null ){ cur.next = l1_cur; } if( l2_cur != null ){ cur.next = l2_cur; } return head; }新闻热点
疑难解答
