关键内容：双指针链表应用，空指针情况考虑
首先，还是那句话，链表的操作可以先设置一个虚拟头节点，也可以直接对原链表操作。这次刷题过程中学到了对于链表使用双指针的思路
其次，链表的题目画画图，想想清楚大致逻辑，即可。
24.想清楚了不难
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dp=new ListNode(0,head); //必须设立虚拟头节点，因为第一个节点变了，返回的时候要当心不要返回head（第一次的错误）
ListNode* e=dp;
if (head==NULL) //特殊情况的考虑
{
return NULL;
}
if (head->next==NULL)
{
return head;
}
ListNode* pre=head;
ListNode* cur=head->next;
ListNode* tmp=cur->next;
while(pre!=NULL)
{
if(pre->next==NULL)
{
return dp->next;
}
cur=pre->next;
tmp=cur->next; //此处创建一个变量，保存起来，方便后面=操作
cur->next=pre;
pre->next=tmp;
e->next=cur;
e=pre;
pre=pre->next;
}
return dp->next;
}
};
19.第一次做此题是算它是正序第几个，第二次采用了双指针的方法，快指针先移动n，随后快慢一起动
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head->next==NULL)
{
return NULL;
}
ListNode* slow=head;
ListNode* fast=head;
for (int i=0;i<n;i++)
{
fast=fast->next;
}
if(fast==NULL) //此处情况便是删除第一个节点，这种情况下不单独考虑，后面fast->next便会出先内存错误。
{
ListNode* p=head->next;
head->next=NULL;
return p;
}
while(fast->next!=NULL)
{
slow=slow->next;
fast=fast->next;
}
ListNode* p=slow->next->next;
slow->next->next=NULL;
slow->next=p;
return head;
}
};
142.自己写的解法，创建了vector对象，元素类型为val地址，即int*
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
vector<int*> p; //开始元素类型写了int，int地址应为int*
ListNode* tmp=head;
while(tmp!=NULL)
{
//p.push_back(&(p->val));
for (int i=0;i<p.size();i++)
{
if(&(tmp->val)==p[i])
{
ListNode* e=head;
for( int j=0;j<i;j++)
{
e=e->next;
}
return e;
}
}
p.push_back(&(tmp->val));
tmp=tmp->next;
}
return NULL;
}；
}
一下借用carl的代码来阐述快慢指针做法：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2; // 返回环的入口
}
}
return NULL;
}
};
总结：
对于快慢指针用法，可以拓展一下思路，比如19题删除倒数n个节点；
链表中最容易出现与空指针相关的错误，这往往是由于忽略特殊情况或是代码的细节没有处理好；
处理链表画画图，想清楚逻辑，事半功倍。