Redian新闻
>
leetcode上的Sort List那道题
avatar
leetcode上的Sort List那道题# JobHunting - 待字闺中
y*3
1
到底咋个写法?谁能给贴个code?我就想不通,linkedlist的in-place merge sort怎
么能到O(n log n)呢??又不是array
avatar
f*3
2
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode tail = head.next;
while (tail.next != null) {tail = tail.next;}
HeadTail ret = sort(head, tail);
return ret.head;
}

class HeadTail {
ListNode head;
ListNode tail;
public HeadTail(ListNode head, ListNode tail) {
this.head = head;
this.tail = tail;
}
}

public HeadTail sort(ListNode head, ListNode tail) {
if (head == tail) {
tail.next = null;
return new HeadTail(head, tail);
}
ListNode fast = head.next;
ListNode slow = head;
while (fast != tail) {
fast = fast.next;
if (fast != tail) {
fast = fast.next;
slow = slow.next;
}
}
ListNode rightHead = slow.next;
HeadTail left = sort(head, slow);
HeadTail right = sort(rightHead, tail);
//merge
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
ListNode p1 = left.head;
ListNode p2 = right.head;
while (p1 != null || p2 != null) {
if ((p1 != null && p2 != null && p1.val < p2.val) || p2 == null)
{
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
p.next = null;
return new HeadTail(dummy.next, p);
}
}

【在 y*****3 的大作中提到】
: 到底咋个写法?谁能给贴个code?我就想不通,linkedlist的in-place merge sort怎
: 么能到O(n log n)呢??又不是array

avatar
y*3
3
比较有创意,你自己想起来的啊?我现在在网上还没找到一个比较统一的、流行的解法
。谢谢分享!

【在 f**********3 的大作中提到】
: public class Solution {
: public ListNode sortList(ListNode head) {
: if (head == null || head.next == null) return head;
: ListNode tail = head.next;
: while (tail.next != null) {tail = tail.next;}
: HeadTail ret = sort(head, tail);
: return ret.head;
: }
:
: class HeadTail {

avatar
d*n
6
那constant space complexity呢? recursion的堆栈深度就是lgn了。

【在 f**********3 的大作中提到】
: public class Solution {
: public ListNode sortList(ListNode head) {
: if (head == null || head.next == null) return head;
: ListNode tail = head.next;
: while (tail.next != null) {tail = tail.next;}
: HeadTail ret = sort(head, tail);
: return ret.head;
: }
:
: class HeadTail {

avatar
s*7
7
这道题用recursion merge sort要容易得多, 也能通过leetcode的oj
如果要一定iterative, bottom-up,要预判各种极端情况, 非常繁琐,面试的那一个小
时估计搞不出来,我写了一会就放弃了, 不钻牛角尖。
有时候bottom up 和 top down 算法上都可行,可coding 两者起来就差老远了
avatar
b*p
8
我来贴个CPP的(注意:以下有乱七八糟的code……)
合并排序确实比较好用,我还在写第一遍leetcode,代码风格也比较乱,带了很多
debug code,还带了测试用例,试了9次才通过…
有一些多边界条件需要判断的。我的方法是加很多debug,或加很多assertion(我做别
的题里面经常用assertion……不知道是不是好习惯)
============================
#include
#include
using namespace std;
/*
Merge sort ?
*/
// Start: 22:40
// End: 23:45 用了一个小时
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
#define TOMMYDBG
class Solution {
public:
ListNode* sort(ListNode* start, ListNode* end, ListNode** new_end) {
int s_val = (start==NULL) ? -999 : start->val;
int e_val = (end == NULL) ? -999 : end->val;
#ifdef TOMMYDBG
printf("%p %p (%d %d)\n", start, end, s_val, e_val);
#endif
ListNode* mid = start, *prev_mid=NULL, *fast = start;
while(true) {
if(fast == end) break;
if(fast != NULL) fast = fast->next;
if(fast == end) break;
if(fast != NULL) fast = fast->next;
prev_mid = mid;
if(mid != NULL) mid = mid->next;
}
#ifdef TOMMYDBG
printf("%p %p %p\n", start, mid, end);
#endif
// 1. sort sublists
ListNode* new_prev_mid = NULL;
if(start != mid and start->next != mid) {
start = sort(start, mid, &new_prev_mid);
}
if(mid != end and mid->next != end) {
ListNode* new_mid = sort(mid, end, NULL);
if(new_prev_mid != NULL)
new_prev_mid->next = new_mid;
if(start->next == mid) {
start->next = new_mid;
}
mid = new_mid;
}
// 2. merge sorted sublists
ListNode* p1=start, *p2=mid, *prev=NULL, *prev_prev = NULL, *p1_end=
mid, *p2_end=end;
#define PRINTNODE(x) { if(x==NULL) { printf("(nil) "); } else {
printf("%d ", x->val); }}
#ifdef TOMMYDBG
printf("Merge ");
PRINTNODE(start);
PRINTNODE(mid);
PRINTNODE(end);
ListNode* x = start;
printf(" List contents >> ");
while(x != end) {
printf("%d ", x->val);
x=x->next;
}
printf("\n");
#endif
ListNode* new_head = start;
if(1) {
while(true) {
#ifdef TOMMYDBG
if(prev!=NULL)
printf("%d ", prev->val);
#endif
if(prev_prev == NULL and prev != NULL) {
new_head = prev;
#ifdef TOMMYDBG
printf("new head is %d\n", new_head->val);
#endif
}
prev_prev = prev;
if(p1 == p1_end and p2 == p2_end) break;
if(p1 == p1_end and p2 != p2_end) {
if(prev != NULL) { prev->next = p2; }
prev = p2;
p2 = p2->next;
} else if(p2 == p2_end and p1 != p1_end) {
if(prev != NULL) { prev->next = p1; }
prev = p1;
p1 = p1->next;
} else {
if(p1->val > p2->val) {
if(prev != NULL) { prev->next = p2; }
prev = p2;
p2 = p2->next;
} else {
if(prev != NULL) { prev->next = p1; }
prev = p1;
p1 = p1->next;
}
}
}
#ifdef TOMMYDBG
printf("new end is %d\n", prev->val);
#endif
prev->next = end;
if(new_end != NULL) {
*new_end = prev;
if(start->next == end) {
*new_end = start; // {3,4,1}
}
}
}
return new_head;
}
ListNode *sortList(ListNode *head) {
if(head==NULL) return NULL;
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
return sort(head, NULL, NULL);
}
};
void printList(ListNode* n) {
while(!(n==NULL)) {
printf("%d ", n->val);
n = n->next;
}
printf("\n");
}
int main() {
Solution sln;
{
ListNode* n1 = new ListNode(1);
ListNode* n3 = new ListNode(3);
ListNode* n4 = new ListNode(4);
n3->next = n4;
n4->next = n1;
printList(n3);
ListNode* newh = sln.sortList(n3);
printList(newh);
}
}
avatar
s*u
9
就利用merge two sorted lists那题的函数啊
ListNode *sortList(ListNode *head, int size){

if(size<=1) return head;

ListNode *prev = NULL, *cur = head;

for(int i = 0; i < size/2; i++){
prev = cur;
cur = cur->next;
}

if(prev) prev->next = NULL;

return mergeTwoLists( sortList(head,size/2), sortList(cur,size -
size/2) );

}

ListNode *sortList(ListNode *head) {

int len = 0;

ListNode *cur = head;

while(cur){
len++;
cur = cur->next;
}

return sortList(head,len);


}
avatar
S*6
10
pass了,不过不是replace
class Solution {
public:
ListNode *sortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vector res;
if(head == NULL || head->next == NULL) return head;
ListNode *cur = head;
while(cur)
{
res.push_back(cur->val);
cur = cur->next;
}
sort(res.begin(), res.end());
ListNode *node = new ListNode(res[0]);
ListNode *n = node;
for(int i = 1; i < res.size(); i++)
{
ListNode *n1 = new ListNode(res[i]);
node->next = n1;
node = node->next;
}
return n;
}
};
avatar
s*x
11

My god, please stop use the judge and figure out the real algorithm first.

【在 S******6 的大作中提到】
: pass了,不过不是replace
: class Solution {
: public:
: ListNode *sortList(ListNode *head) {
: // IMPORTANT: Please reset any member data you declared, as
: // the same Solution instance will be reused for each test case.
: vector res;
: if(head == NULL || head->next == NULL) return head;
: ListNode *cur = head;
: while(cur)

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。