to do
1] Merge Sorted Array
注意comment out的一句可省
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int write = m+n-1; // pos to write the next one
int read1 = m-1;
int read2 = n-1;
while (read1!=-1 && read2!=-1) {
if (nums1[read1]>nums2[read2]) {
nums1[write--] = nums1[read1--];
} else {
nums1[write--] = nums2[read2--];
}
}
// while (read1!=-1) nums1[write--] = nums1[read1--];
while (read2!=-1) nums1[write--] = nums2[read2--];
}
2] Merge Two Sorted Lists
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 || !l2) return l1? l1 : l2;
ListNode dummy = ListNode(-1);
ListNode* curr = &dummy;
for (; l1&&l2; curr=curr->next) {
if (l1->val < l2->val) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
}
if (l1 || l2) curr->next = l1? l1 : l2;
return dummy.next;
}
2] see below
3] Merge k Sorted Lists
ListNode* mergeTwo (ListNode* l1, ListNode* l2) {
if (!l1 || !l2) return l1? l1 : l2;
ListNode dummy = ListNode(-1);
ListNode* curr=&dummy;
for (; l1&&l2; curr=curr->next) {
if (l1->val < l2->val) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
}
curr->next = l1? l1 : l2;
return dummy.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
ListNode* ret = nullptr;
for (int i=0; i<lists.size(); ++i) {
ret = mergeTwo(ret, lists[i]);
}
return ret;
}
3] Merge k Sorted Lists
学会分析下bigO。。另外mergeTwo的居然是recursion的更快，recursion stack的时空间分析回头来
- iterate through all lists in search for next-to-insert
- merge each list with
ret - partition then merge：
O(nlogk): split takes O(logk), merge takes O(n)??
ListNode* mergeTwo (ListNode* l1, ListNode* l2) {
if (!l1 || !l2) return l1? l1 : l2;
if (l1->val < l2->val) {
l1->next = mergeTwo(l1->next, l2);
return l1;
} else {
l2->next = mergeTwo(l1, l2->next);
return l2;
}
return nullptr;
}
ListNode* splitNmergeR(vector<ListNode*>& lists, int l, int r) {
if (l>r) return nullptr;
if (l==r) return lists[l];
if (l+1==r) return mergeTwo(lists[l], lists[r]);
int mid = (l+r)/2;
return mergeTwo(splitNmergeR(lists, l, mid-1), splitNmergeR(lists, mid, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return splitNmergeR(lists, 0, lists.size()-1);
}
4] Insertion Sort List
mark redo X( 流程图
ListNode* insertionSortList(ListNode* head) {
if (!head) return nullptr;
ListNode dummy = ListNode (-1);
dummy.next = head;
ListNode* tail = head;
for (ListNode* curr=head->next, *nextCurr; curr; curr=nextCurr) {
nextCurr=curr->next;
tail->next = nullptr;
bool inserted = false;
for (ListNode* prev=&dummy; prev!=tail; prev=prev->next) {
if (prev->next->val >= curr->val) {
curr->next = prev->next;
prev->next = curr;
inserted = true;
break;
}
}
if (!inserted) {
curr->next = nullptr;
tail->next = curr;
tail = curr;
}
}
return dummy.next;
}
5] Sort List
beat 95% hhh, 把for loop body变为afterthought就跌成6%了有意思
ListNode* mergeTwo(ListNode* l1, ListNode* l2) {
if (!l1 || !l2) return l1? l1: l2;
if (l1->val < l2->val) {
l1->next = mergeTwo(l1->next, l2);
return l1;
} else {
l2->next = mergeTwo(l1, l2->next);
return l2;
}
return nullptr;
}
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* slow=head;
for (ListNode* fast=head; fast->next && fast->next->next; ) {
fast = fast->next->next;
slow = slow->next;
}
ListNode* l2 = slow->next;
slow->next = nullptr;
return mergeTwo(sortList(head), sortList(l2));
}
7] Sort Colors
double ptrs
void sortColors(vector<int>& nums) {
int red = 0, blue = nums.size()-1;
for (int j=0; j<=blue; ) {
if (nums[j]==0) {
nums[red++] = nums[j++];
} else if (nums[j]==2) {
swap(nums[blue--], nums[j]);
} else {
++j;
}
}
for (int i=red; i<=blue; ++i) nums[i]=1;
}
