24. 两两交换链表中的节点
这道题也太绕了，本身倒是不难，我也差点写出来了。这回倒是想起来先创建dummy_head来操作了。可还是没写出来，这道题还得练几遍。链表的题的确是需要画图才能想清楚一些。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy_head = new ListNode(-1, head);
ListNode* cur = dummy_head;
while((cur->next != nullptr) && (cur->next->next != nullptr)){
ListNode* tmp = cur->next;
ListNode* tmp1 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = tmp;
cur->next->next->next = tmp1;
cur = cur->next->next;
}
return dummy_head->next;
}
};
19.删除链表的倒数第N个节点
虽然是用的笨办法，但是还是一次就做出来啦！还是很开心的。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy_head = new ListNode(-1, head);
ListNode* cur = dummy_head;
int size = 1;
while(cur->next != nullptr){
cur = cur->next;
size++;
}
cur = dummy_head;
int step = size - n;
while(--step){
cur = cur->next;
}
if(n!=1){
cur->next = cur->next->next;
}
else{
cur->next = nullptr;
}
return dummy_head->next;
}
};
在做笨办法之前，考虑过只遍历一次的话，该怎么写但是没想出来。把笨方法写出来之后，有了信心，一口气也把遍历一次链表的方法完全自己的写出来了。写之前在纸上画了好几个案例，发现用图的话，的确是会思路清晰很多。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy_head = new ListNode(-1, head);
ListNode* cur = dummy_head;
while(n>0){
cur = cur->next;
n--;
}
ListNode* pre = dummy_head;
while(cur->next!=nullptr){
pre = pre->next;
cur = cur->next;
}
if(n == 1){
pre->next = nullptr;
}
else{
pre->next = pre->next->next;
}
return dummy_head->next;
}
};
面试题 02.07. 链表相交
多亏了做题前看了今日安排里的题目提示，提醒了我两个链表光是数值一样那不一定就是相交的点，必须是node一样才行。我的想法就是用hashset来储存一个链表的所有点，然后再遍历第二个链表。可行是可行，就是用了太多资源了。(Runtime: 64 ms Memory Usage: 17.3 MB)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* result = nullptr;
ListNode* a_ptr = headA;
unordered_set<ListNode*> uset;
while(a_ptr != nullptr){
uset.insert(a_ptr);
if(a_ptr->next != nullptr)
a_ptr = a_ptr->next;
else
a_ptr = nullptr;
}
ListNode* b_ptr = headB;
while(b_ptr != nullptr){
auto it = uset.find(b_ptr);
if(it != uset.end())
return b_ptr;
else
{
if(b_ptr->next != nullptr)
b_ptr = b_ptr->next;
else
b_ptr = nullptr;
}
}
return result;
}
};
写完后看了Carl的解析。他是利用了两个链表一旦相交了，那么他们所相交的部分肯定是一样长的，不存在又分开的情况。所以，先求出两个链表的长度，然后把短的链表的尾部挪到和长链表平齐，然后两个指针分别指向两个链表，如果两个指针的node不同，那么就一起后移一位。这么做的确是聪明。
142.环形链表II
这一题我同样用的是哈希表来储存经历过的node，然后一旦遇到哈希表里已有的node，那么就说明这个node是环形链表的头。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* res = nullptr;
ListNode* cur = head;
unordered_set<ListNode*> uset;
while(cur != nullptr){
auto it = uset.find(cur);
if(it != uset.end()){
res = cur;
break;
}
else{
uset.insert(cur);
cur = cur->next;
}
}
return res;
}
};
这道题用双指针的写法，还是有些糊涂，需要多看几遍。
