19. Remove Nth Node From End of List
- 教你如何巧妙地使用双指针，我自己用的还是不够灵活啊
- 里面有个关于单向链表结点的删除可以注意一下
- 此题不难
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode newhead(0);
newhead.next = head;
ListNode* slow = &newhead;
ListNode* fast = &newhead;
for (int i=0;i<n;i++) fast= fast->next;
while(fast->next){
slow=slow->next;
fast=fast->next;
}
ListNode* d = slow->next;
slow->next = slow->next->next;
delete d;
return newhead.next;
}
};
23. Merge k Sorted Lists
这道题乍一看好像是HARD的，有点唬人，实际上一点都不难。。。考察的点貌似就两个
- 首先是对于MergeTwoSortedLists的练习，这个已经熟得不能再熟了
- 然后是稍微考察了一点vector的知识（当然，为了时间复杂度低一点，尽量还是不使用vector自带的push_back，erase等命令啦）
- 这里就用了两循环，不停减少len的长度，本菜鸡目测时间复杂度应该是o(nlogn)？
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2){
ListNode dummy(0);
ListNode* head = &dummy;
while(l1&&l2){
if (l1->val < l2->val){
head->next = l1;
l1 = l1->next;
}
else{
head->next = l2;
l2= l2->next;
}
head = head->next;
}
head->next = l1 ? l1 : l2;
return dummy.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
int len = lists.size();
while(len>1){
for(int i =0;i<len/2;i++)
lists[i] = merge(lists[i], lists[len-i-1]);
len = (len+1)/2;
}
return lists.front();
}
};
