【LintCode】Sort List（笔记）

Description

Sort a linked list in O(n log n) time using constant space complexity.

Example

Given 1->3->2->null, sort it to 1->2->3->null.

Notes

主要思想就是如何对链表作归并排序。

1.归并排序的思想

2.寻找链表的中间结点（弄两个指针,每次循环p1->next,p2->next->next,p2到达终结点时p1就是中间结点）

3.合并两个已排序链表（合并后的链表注意要有末尾null,为了下一次合并）

Solution

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /* * @param head: The head of linked list. * @return: You should return the head of the sorted linked list, using constant space complexity. */ ListNode * sortList(ListNode * head) { // write your code here if(head==NULL || head->next==NULL) return head; return mergeList(head); } ListNode * mergeList(ListNode *head){ if(head==NULL || head->next==NULL) //递归终点注意 return head; ListNode *lh=head; ListNode *rh; ListNode *p1=head, *p2=head->next; while(p2!=NULL && p2->next!=NULL){ p1 = p1->next; p2 = p2->next->next; } rh = p1->next; p1->next = NULL; ListNode *lhalf = mergeList(lh); ListNode *rhalf = mergeList(rh); return merge(lhalf, rhalf); } ListNode * merge(ListNode *lh, ListNode *rh){ ListNode *sh; if(lh->val<=rh->val){ //解决表头问题 sh = lh; lh = lh->next; } else{ sh = rh; rh = rh->next; } ListNode *p = sh; //指针p指向表头 while(lh&&rh){ if(lh->val<=rh->val){ p->next = lh; lh = lh->next; } else{ p->next = rh; rh = rh->next; } p = p->next; //链表指针要移动 } if(lh!=NULL) //merge后要有终点,为了下一次合并 p->next = lh; else p->next = rh; return sh; } };

这里的merge函数我原先怎么都不能AC的错误写法↓

 

ListNode * merge(ListNode *lh, ListNode *rh){ ListNode *sh; ListNode *p = sh; //p这里不能指向sh if(lh->val<=rh->val){ p = lh; lh = lh->next; } else{ p = rh; rh = rh->next; } while(lh&&rh){ if(lh->val<=rh->val){ p->next = lh; lh = lh->next; } else{ p->next = rh; rh = rh->next; } p = p->next; } if(lh!=NULL) p->next = lh; else p->next = rh; return sh; }

如果我一开始让sh申请内存建个链表头，而不是空指针，就不会有这种错了。

 

下面的merge函数是正确的写法↓

 

ListNode * merge(ListNode *lh, ListNode *rh){ ListNode *sh = new ListNode(0); ListNode *p = sh; //这样p指向sh就没问题了,而且没有表头问题 while(lh&&rh){ if(lh->val<=rh->val){ p->next = lh; lh = lh->next; } else{ p->next = rh; rh = rh->next; } p = p->next; } if(lh!=NULL) p->next = lh; else p->next = rh; p = sh->next; sh->next = NULL; delete sh; //把占用内存释放掉 return p; }