b*******n
发帖数: 8 | 1 做了这道题，被accepted, 但觉得代码很罗嗦冗长。
怎么改进呢？
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class ListNodeWrapper {
ListNode start;
ListNode end;
}
public class Solution {
private ListNode partionList(ListNode start, ListNode end) {
ListNode end1 = start;
ListNode fast = start;
while (fast != end) {
fast = fast.next;
if (fast != end) {
fast = fast.next;
end1 = end1.next;
}
}
return end1;
}
private ListNodeWrapper merge(ListNode start1, ListNode end1, ListNode
start2, ListNode end2) {
ListNode ln1 = start1;
ListNode ln2 = start2;
ListNode ln;
ListNodeWrapper lnw = new ListNodeWrapper();
if (ln1.val <= ln2.val) {
ln = ln1;
ln1 = ln1.next;
} else {
ln = ln2;
ln2 = ln2.next;
}
lnw.start = ln;
while (ln != end1 && ln != end2) {
if (ln1.val <= ln2.val) {
ln.next = ln1;
ln = ln.next;
ln1 = ln1.next;
} else {
ln.next = ln2;
ln = ln.next;
ln2 = ln2.next;
}
}
if (ln == end1) {
ln.next = ln2;
lnw.end = end2;
} else {
ln.next = ln1;
lnw.end = end1;
}
lnw.end.next = null;
return lnw;
}
private ListNodeWrapper mergeSort(ListNode start, ListNode end) {
ListNodeWrapper lnw = new ListNodeWrapper();
if (start == end) {
lnw.start = start;
lnw.end = end;
return lnw;
}
ListNode end1 = partionList(start, end);
ListNode start2 = end1.next;
ListNodeWrapper lnw1 = mergeSort(start, end1);
ListNodeWrapper lnw2 = mergeSort(start2, end);
lnw = merge(lnw1.start, lnw1.end, lnw2.start, lnw2.end);
return lnw;
}
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.
if (head == null) return null;
ListNode end = head;
while(end.next != null) end = end.next;
ListNodeWrapper lnw = mergeSort(head, end);
return lnw.start;
}
} | w**t
发帖数: 893 | 2 use a array to hold the intermediate results, merge them whenever a new
entry come and move it to next empty slot
【在 b*******n 的大作中提到】
: 做了这道题，被accepted, 但觉得代码很罗嗦冗长。
: 怎么改进呢？
: /**
: * Definition for singly-linked list.
: * class ListNode {
: * int val;
: * ListNode next;
: * ListNode(int x) {
: * val = x;
: * next = null;
| h*z
发帖数: 33 | 3 C++ looks shorter.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
if (!head || !head->next) return head;
ListNode *slow = head;
ListNode *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *p = slow->next;
slow->next = nullptr;
return merge(sortList(head), sortList(p));
}
private:
ListNode *merge(ListNode *p, ListNode *q) {
ListNode sentil(0);
ListNode *r = &sentil;
while (p && q) {
if (p->val > q->val) {
r->next = q;
q = q->next;
} else {
r->next = p;
p = p->next;
}
r = r->next;
}
if (p) r->next = p;
if (q) r->next = q;
return sentil.next;
}
}; | g*********e
发帖数: 14401 | 4 我的也很长，但不用每个recursion都寻找中间node的位置。
class Solution {
public:
ListNode *merge(ListNode *a, ListNode *b, ListNode *&last) {
ListNode *res=NULL;
ListNode *prev=NULL;
while(a && b) {
if(res==NULL)
res=(a->val < b->val) ? a:b;
if(a->val < b->val) {
if(prev)
prev->next=a;
prev=a;
a=a->next;
} else {
if(prev)
prev->next=b;
prev=b;
b=b->next;
}
}
while(a) {
prev->next=a;
prev=prev->next;
last=prev;
a=a->next;
}
while(b) {
prev->next=b;
prev=prev->next;
last=prev;
b=b->next;
}
return res;
}
ListNode *mySortList(ListNode *&head, ListNode *&prev, int len) {
if(len==1) {
//if(prev)
// prev->next=head;
prev=head;
head=head->next;
return prev;
}
int lena=len/2;
int lenb=len-lena;
ListNode *aPrev=prev;
ListNode *left=mySortList(head, prev, lena);
ListNode *aTail=prev;
ListNode *right=mySortList(head, prev, lenb);
ListNode *bTail=prev;
aTail->next=NULL; bTail->next=NULL;
ListNode *last=NULL;
ListNode *merged=merge(left, right, last);
if(aPrev)
aPrev->next=merged;
last->next=head;
prev=last;
return merged;
}
ListNode *sortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ListNode *prev=NULL;
int cnt=0;
ListNode *t=head;
while(t) {
t=t->next; cnt++;
}
if(cnt==0)
return NULL;
return mySortList(head, prev, cnt);
}
}; | m*******n
发帖数: 103 | | m*******n
发帖数: 103 | 6 偶没有看过leetcode，楼上几位都用merge sort是有什么原因吗？ | d**********x
发帖数: 4083 | 7 nlogn
【在 m*******n 的大作中提到】
: 偶没有看过leetcode，楼上几位都用merge sort是有什么原因吗？
| m********c
发帖数: 105 | 8 写了一个iterative method，参考了这个 http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
ListNode *sortList(ListNode *head) {
if (head == NULL)
return head;
int width = 1, firstSize, secondSize;
ListNode *tail;
while (true) {
ListNode *first = head;
ListNode *curr;
int nmerge = 0;
tail = NULL;
while (first) {
ListNode *second = first;
firstSize = 0;
nmerge++;
for (int i=0; i
second = second->next;
firstSize++;
if (second == NULL)
break;
}
secondSize = width;
while (firstSize > 0 || (secondSize > 0 && second)) {
if (first == 0) {
curr = second;
second = second->next;
secondSize--;
}
else if (secondSize == 0 || second == NULL) {
curr = first;
first = first->next;
firstSize--;
}
else if (first->val <= second->val) {
curr = first;
first = first->next;
firstSize--;
}
else {
curr = second;
second = second->next;
secondSize--;
}
if (tail == NULL) {
head = curr;
tail = head;
}
else {
taill->next = curr;
tail = tail->next;
}
} // end of merge lists
first = second;
} // end of this width
tail->next = NULL;
if (nmerge <= 1)
return head;
width *= 2;
}
} | c********w
发帖数: 2438 | 9 我po个我的
public class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode slow=head;
ListNode fast=head.next;
while(fast!=null){
fast=fast.next;
if(fast!=null){
fast=fast.next;
slow=slow.next;
}
}
ListNode h1=head;
ListNode h2=slow.next;
slow.next=null;
h1=sortList(h1);
h2=sortList(h2);
return merge(h1, h2);
}
private ListNode merge(ListNode h1, ListNode h2){
ListNode dummy=new ListNode(-1);
dummy.next=h1;
ListNode d=dummy;
while(h1!=null&&h2!=null){
if(h1.val>=h2.val){
ListNode t=h2;
h2=h2.next;
while(d.next!=h1)
d=d.next;
t.next=h1;
d.next=t;
}
else
h1=h1.next;
}
if(h2!=null){
while(d.next!=null)
d=d.next;
d.next=h2;
}
return dummy.next;
}
} | s**x
发帖数: 7506 | 10 better split into more functions like geeksforgeeks
http://www.geeksforgeeks.org/merge-sort-for-linked-list/
also, I do not think we really need to split the list to half and half first
, need to a similar way for converting single linked list to BST,
from bottom up, move the list accordingly.
still nlogn though. | b*******e
发帖数: 123 | | d****n
发帖数: 233 | 12 Similar to yours but shorter:
ListNode *merge(ListNode *a,ListNode *b) {
ListNode sentil(0);
ListNode *r = &sentil;
while (a && b) {
if (a->val > b->val) {
r->next = b;
b = b->next;
} else {
r->next = a;
a = a->next;
}
r = r->next;
}
if (a) r->next = a;
if (b) r->next = b;
return sentil.next;
}
ListNode *mySortList(ListNode *&head, int len) {
if (len == 1) {
ListNode *tmp = head;
head = head->next;
tmp->next = NULL;
return tmp;
}
int lena=len/2;
int lenb=len-lena;
ListNode *a=mySortList(head, lena);
ListNode *b=mySortList(head, lenb);
ListNode *merged=merge(a, b);
return merged;
}
ListNode *sortList(ListNode *head) {
int cnt=0;
ListNode *t=head;
while(t) {
t=t->next; cnt++;
}
if(cnt <=1)
return head;
return mySortList(head, cnt);
}
【在 g*********e 的大作中提到】
: 我的也很长，但不用每个recursion都寻找中间node的位置。
: class Solution {
: public:
: ListNode *merge(ListNode *a, ListNode *b, ListNode *&last) {
: ListNode *res=NULL;
: ListNode *prev=NULL;
: while(a && b) {
: if(res==NULL)
: res=(a->val < b->val) ? a:b;
: if(a->val < b->val) {
| t**8
发帖数: 4527 | 13 iterate
for ( step = 1 to lengh/2)
compare and merge
or for ( step = len /2 to 1)
comparre and merge
4 5 2 1 6 8, 3, 7
4,5, 1, 2, 6, 8, 3, 7
1, 2, 4, 5, 3, 7, 6, 8
1, 2, 3, 4, 5, 6, 7, 8
or
4, 5, 2, 1, 6, 8, 3, 7
4, 6, 5, 8, 2, 3, 1, 7
2, 3, 4, 6, 1, 5, 7, 8
1, 2, 3, 4, 5, 6, 7, 8
【在 b*******e 的大作中提到】
: 这个题不用recursion怎么做？
|
|
