w****r 发帖数: 15252 | 1 /*
* Sort a linked list in O(n log n) time using constant space
complexity.
*/
public ListNode sortList(ListNode head) {
if(head == null || head.next == null)
return head;
//get the length of the liklist
int count = 0;
ListNode node = head;
while(node!=null){
count++;
node = node.next;
}
//break up to two list
int middle = count / 2;
ListNode middleNode = head, rightlisthead = null;
int countHalf = 1;
while(countHalf < middle){
countHalf++;
middleNode = middleNode.next;
}
rightlisthead = middleNode.next;
middleNode.next = null;
//recursively break until it can not break
ListNode left = sortList(head);
ListNode right = sortList(rightlisthead);
//combine and return the head of new sorted linkList
return merge(left,right);
}
private static ListNode merge(ListNode leftlist,ListNode rightlist){
ListNode head,currentNode, nextNode;
if(leftlist == null)
return rightlist;
else if(rightlist == null)
return leftlist;
else if(leftlist.val <= rightlist.val){
head = leftlist;
currentNode = leftlist;
nextNode = rightlist;
} else {
head = rightlist;
currentNode = rightlist;
nextNode = leftlist;
}
ListNode temp;
while(nextNode !=null){
if(currentNode.next == null){
currentNode.next = nextNode;
nextNode = null;
}
else if(currentNode.next.val <= nextNode.val){
currentNode = currentNode.next;
} else {
temp = currentNode.next;
currentNode.next = nextNode;
nextNode = temp;
}
}
return head;
} | l****h 发帖数: 1189 | | l*****a 发帖数: 14598 | 3 你写这么长谁有工夫给你看啊?
【在 w****r 的大作中提到】 : /* : * Sort a linked list in O(n log n) time using constant space : complexity. : */ : public ListNode sortList(ListNode head) { : if(head == null || head.next == null) : return head; : : //get the length of the liklist : int count = 0;
|
|