又重新入C ，左右为难啊！# PhotoGear - 摄影器材
w*r
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;
}
* 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;
}
