leetcode上的Sort List那道题# JobHunting - 待字闺中
y*3
1 楼
到底咋个写法？谁能给贴个code？我就想不通，linkedlist的in-place merge sort怎
么能到O(n log n)呢？？又不是array
么能到O(n log n)呢？？又不是array
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
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
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 {
。谢谢分享！
【在 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 {
y*3
5 楼
谢谢！
【在 s**x 的大作中提到】
: http://www.geeksforgeeks.org/merge-sort-for-linked-list/
【在 s**x 的大作中提到】
: http://www.geeksforgeeks.org/merge-sort-for-linked-list/
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 {
【在 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
7 楼
这道题用recursion merge sort要容易得多， 也能通过leetcode的oj
如果要一定iterative, bottom-up,要预判各种极端情况， 非常繁琐，面试的那一个小
时估计搞不出来，我写了一会就放弃了， 不钻牛角尖。
有时候bottom up 和 top down 算法上都可行，可coding 两者起来就差老远了
如果要一定iterative, bottom-up,要预判各种极端情况， 非常繁琐，面试的那一个小
时估计搞不出来，我写了一会就放弃了， 不钻牛角尖。
有时候bottom up 和 top down 算法上都可行，可coding 两者起来就差老远了
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);
}
}
合并排序确实比较好用，我还在写第一遍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
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);
}
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
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;
}
};
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
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
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
: if(head == NULL || head->next == NULL) return head;
: ListNode *cur = head;
: while(cur)
相关阅读
刷题对于有工作经验的, 基本没用这两个人是敌是友？关于投行offer 问题想进入保守地区那些白人主体的公司太难了HERE工作十年体会 – 续篇三北大本科哥大硕士住Palo Alto的F家员工被捕 (转载)替朋友发文，求建议我就不信就我一个人在等待大学工作的录取工作时间很短的公司可以不列在简历上么？[求助] f1转h1b期间被裁比较tricky的身份问题谁来介绍下VR/AR方向的startup ?Google aims to train 2 million app developers in India大家觉得NextEV有前途吗？值得去吗？说说CS转行，毕业10年，大家可以看看Uber's head of HR to join Twitter那些玻璃门评出来的最佳工作公司STARTUP根本就是假的签了offer letter还可以反悔吗？现在入职Yahoo是不是很不明智？Zillow这个公司怎么样？比微软如何呢？你在工作中最看重什么