由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - [ 每日一课] Sort List
相关主题
请大家 看看这个 Merge k Sorted Lists (Java), 我不太明白弱问题,连反转链表都看不懂了
leetcode上的sorted list to BST弱问:leetcode里Convert Sorted List to Binary Search Tree
大牛们帮忙,Rverse Nodes in k-Group弱问一个小问题,leetcode 上merge sorted list
reverse linked list 问题, double 和 single 的不同这题怎么做?
一个stack怎么sort透露两个G的onsite题
一道挺简单的题给搞砸了leetcode上的Sort List那道题
leetcode过的一代工程师[BSSD]回国一趟回来做题很难进入状态了,顺便问下那个Merge k Sorted
怎么理解递归解决的“swap every two elements in a linked list”?【我自己写的LinkedList为什么总有错?】
相关话题的讨论汇总
话题: listnode话题: nextnode话题: null话题: head话题: rightlist
进入JobHunting版参与讨论
1 (共1页)
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
2
贴code不如总结几个要点好。
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;

1 (共1页)
进入JobHunting版参与讨论
相关主题
【我自己写的LinkedList为什么总有错?】一个stack怎么sort
请教一道单链表问题一道挺简单的题给搞砸了
看不懂这题leetcode过的一代工程师
明天电面,求建议怎么理解递归解决的“swap every two elements in a linked list”?
请大家 看看这个 Merge k Sorted Lists (Java), 我不太明白弱问题,连反转链表都看不懂了
leetcode上的sorted list to BST弱问:leetcode里Convert Sorted List to Binary Search Tree
大牛们帮忙,Rverse Nodes in k-Group弱问一个小问题,leetcode 上merge sorted list
reverse linked list 问题, double 和 single 的不同这题怎么做?
相关话题的讨论汇总
话题: listnode话题: nextnode话题: null话题: head话题: rightlist