y*****3
发帖数: 451 | 1 到底咋个写法？谁能给贴个code？我就想不通，linkedlist的in-place merge sort怎
么能到O(n log n)呢？？又不是array | f**********3
发帖数: 295 | 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
| y*****3
发帖数: 451 | 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 {
| s**x
发帖数: 7506 | | y*****3
发帖数: 451 | | d****n
发帖数: 397 | 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 {
| s******7
发帖数: 1758 | 7 这道题用recursion merge sort要容易得多， 也能通过leetcode的oj
如果要一定iterative, bottom-up,要预判各种极端情况， 非常繁琐，面试的那一个小
时估计搞不出来，我写了一会就放弃了， 不钻牛角尖。
有时候bottom up 和 top down 算法上都可行，可coding 两者起来就差老远了 | b******p
发帖数: 49 | 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);
}
} | s********u
发帖数: 1109 | 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);
} | S******6
发帖数: 55 | 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;
}
}; | s**x
发帖数: 7506 | 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)
|
|
