题目：24.两两交换链表中的节点
思路：
设置虚拟头结点，双指针+临时指针，(感觉也能递归,未尝试）
时间复杂度：O(n)
空间复杂度：O(1)
坑：
1.又忘了 else{}和return
2.试图访问空指针，多个条件的顺序问题及"&&""||"问题，cur->next要写在cur->next->next前面
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr)
return head;
else {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* cur = dummyhead;
ListNode* post = head;
ListNode* pre = new ListNode(0);
ListNode* tmp;
while (cur->next!=nullptr&&cur->next->next!=nullptr) { //优化后，报错，
/*1. 是“&&”不是“||”, 或的话，若cur->next为nullptr，则cur->next->next就访问空指针了，
2.cur->next要写在cur->next->next前面，理由同上
*/
pre = post->next;
tmp = pre->next;
cur->next = pre;
pre->next = post;
post->next=tmp; //提交heap-use-after-free报错了，我的链表交换后，这里断了,
cur = post;
post = tmp;
}
return dummyhead->next;
}
}
};
/*未优化版本
while (post!=nullptr) { //可优化，循环结束条件不对，看循环体结束部分来思考
pre = post->next;
if(pre==nullptr){ //缺少判断条件 长度为奇数的链表 这部分可优化
return dummyhead->next;
}
tmp = pre->next;
cur->next = pre;
pre->next = post;
post->next=tmp; //提交heap-use-after-free报错了，我的链表交换后，这里断了,
cur = post;
post = tmp;
}
*/
补充：
1.heap-use-after-free on address
尾节点如果没有rear->next=NULL;这个链表就会错呢？ 尾节点没有明确指向，链表不完整，计算机认为链表未结束
2.悬挂指针（Dangling Pointer）。如果我们试图访问已经被释放的内存，就会触发"heap-use-after-free"错误。
题目：19.删除链表的倒数第N个节点
思路：
1.遍历链表获取链表长度，然后删除结点，释放被删除节点
2.进阶要求是，使用一趟扫描实现-->随想录思路 啊 是快慢指针，快指针先走N+1步，
时间复杂度: O(n)
空间复杂度: O(1)
坑：
试图访问空指针，主要在cur->next时，cur可能为空指针
/** Definition for singly-linked list.同上*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead=new ListNode(0);
dummyHead->next=head;
ListNode* fast=dummyHead; //fast和slow初始指向虚拟head不是head
ListNode* slow=dummyHead;
ListNode* tmp;
n++; //删除结点，slow要指向被删除结点的前一个节点，所以fast要多走一步，slow和fast相差n+1步
while(n--&&fast!=nullptr){ //错误，需要判断fast是否为空，
fast=fast->next;
}
while(fast!=nullptr){ //错误，试图访问空指针 fast不为空 不用->next
fast=fast->next;
slow=slow->next;
}
tmp=slow->next;
slow->next=slow->next->next;
delete tmp;
return dummyHead->next;
}
};
补充：
个人对快慢双指针还是没有理解到位
双指针解题：
1.指针相邻：删除某个结点，或交换两个结点
2.指针不相邻，快满指针间隔N步
题目：面试题02.07.链表相交
思路：
1.两个这指针分别指向a,b，两层循环遍历，比较->next是否相等，有点繁琐
2.看了leetcode的引导式提示：从两链表长度相同时相交到不同长度，一个先走差值步，使得二者相同才判断；
时间复杂度：O(n + m)
空间复杂度：O(1)
坑：
- 当两链表长度相同时，两链表不相交可以和相交放一起判断
- 使用pa->next判空，则少算了最后一个pa节点
- 没比较两链表长度，就默认进行下去了；
/** Definition for singly-linked list.同上*/
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* pA = headA;
ListNode* pB = headB;
int m = 0, n = 0, diff = 0; // diff表示两链表的差值 （用英语gap也行）
pA = headA; // 指针返回头结点
pB = headB;
while (pA != nullptr) { // 错误,pa->next判空，则少算了最后一个pa节点
pA = pA->next;
m++;
}
while (pB != nullptr) {
pB = pB->next;
n++;
}
pA = headA;
pB = headB;
// 错误，m和n的大小没有判断，
if (m < n) { // 交换使得，pA和m表示较长的链表
swap(pA, pB);
swap(m, n);
}
diff = m - n;
while (diff--) {
pA = pA->next;
}
while (pA!=nullptr) {
if(pA==pB)
return pA;
pA = pA->next;
pB = pB->next;
}
return NULL;
}
};
题目：142.环形链表Ⅱ
思路：
坑：
补充：
今日总结
链表类的题主要还是看思路，想得到关键，就后面很顺利
标签：ListNode,cur,随想录,next,链表,pA,节点,指针 From： https://www.cnblogs.com/bamboo2233/p/18239059