24.两两交换链表中的节点
题目链接：24.两两交换链表中的节点
总体思路：
两两交换链表中的节点使用虚拟头节点可以更方便地进行交换，这样头节点和普通节点可以以同一种方式进行。
虚拟头结点的建设代码：
ListNode* dummyHead=new ListNode(0);
dummyHead->next=head;
交换思路：
- 步骤一：用虚拟头节点连接第二个节点，准备交换
- 步骤二：1、2两节点进行交换
- 步骤三：虚拟头节点向后移两位，准备进行下一组交换
cur->next=cur->next->next;//步骤1
cur->next->next=tmp;//步骤2
cur->next->next->next=tmp1;//步骤3
cur->next既代表着指针域，也代表着下一个节点
、、
代码实现
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
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; // cur移动两位，准备下一轮交换
}
return dummyHead->next;
}
};
bullptr是C++中声明空指针的关键字，cur->next!=nullptr表示current节点的下一个不是空指针，因为cur是虚拟头指针，所以通过cur的移动进行，cur->next->next等同于cur+=2;含义。
由于链表的交换会对切断节点的连接，因此要提前使用tmp、tmp1作为临时节点对2、3号节点进行托管和存放。
19.删除链表的的倒数第N个节点
题目链接: 19.删除链表的的倒数第N个节点
总体思路：
和数组中的移除元素相同，通过快慢指针进行，唯一需要改变的就是从链表最后的节点开始操作，到最开始倒向进行。
在删除节点时仍要考虑是否为头节点，因此设置为虚拟头节点会更方便。
链表的最后一个节点在于其tmp->next=nulltpr。
使用虚拟头节点进行查找。
- 定义fast指针和slow指针，初始值为虚拟头节点
- fast首先走n+1步，这样保证slow在移动时可以指向删除结点的上一个节点，从而使删除更方便
- fast和slow同时移动，直到fast指向末尾
删除slow指向的下个节点
代码实现：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
while(n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
// ListNode *tmp = slow->next; C++释放内存的逻辑
// slow->next = tmp->next;
// delete nth;
return dummyHead->next;
}
};
面试题02.07. 链表相交
题目链接：面试题02.07.链表相交
总体思路：
两个链表相交，需注意，相交不是数值相等，是指针相等。
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
代码实现
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA=headA;
ListNode* curB=headB;
int LenA=0,LenB=0;
while(curA!=NULL){//求链表A的长度
lenA++;
curA=curA->next;
}
while(curB!=NULL){//求链表B的长度
lenB++;
curB=curB->next;
}
curA=headA;
curB=headB;
//让给curA为最长的链表，LenA为其长度
if(lenB>lenA){
swap(LenA,LenB);
swap(curA,curB);
}
//求长度差
int gap=LenA-LenB;
//让A和B在同一起点上（末尾位置对齐）
while(gap--){
curA=curA->next;
}
//遍历curA和curB遇到相同的则返回
while(curA!=NULL){
if(curB==curA){
return curA;
}
curA=curA-next;
curB=curb->next
}
return NULL;
}
};
否则循环退出返回空指针。
- 时间复杂度O(n+m)
- 空间复杂度O(1)
142.环形链表Ⅱ
题目链接：142.环形链表Ⅱ
总体思路
本题主要考察：
- 判断链表是否有环
- 如果有环，如何找到环的入口
判断链表是否有环
使用快慢指针，fastNode每次移动两个节点fastNode=fastNode->next->next，slowNode每次移动一个节点slowNode=slowNode->next，如果相遇if(fastNode==slowNode)，则说明链表有环
如果有环，如何判断入口
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：
相遇时，slow指针走过x+y,fast指针走过x+y+n(y+z),因为在圆内的相遇说明fast一定会比slow快一圈。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：(x+y)*2=x+y+n(y+z) =>x+y=n(y+z)
因为要求的是环的入口，所以即求x的数值，即x=z+(n-1)y ，从n(y+z)提出(y+z)有x=(n-1)(y+z)+z注意，n一定大于1，因为这样fastNode才能比slowNode快一圈。
同时，fast是每次移动两个节点，，slow是每次移动一个节点，所以fast速度作为slow的两倍一定可以与slow相交。
代码实现
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fastNode=head; //定义快节点
LostNode* slowNode=head; //定义慢节点
while(fastNode!=NULL&&fastNode->next!=NULL){
fastNode=fastNode->next->next; //快节点一次移动两个，因为要移动，所以要在while里移动
slowNode=slowNode->next; //慢节点一次移动一个节点
if(slowNode==fastNode){ //当快慢节点重合时
ListNode* index1=fastNode; //
ListNode* index2=slowNode;
while(index1!=index2){
index1=index1->next;//index
index2=index2->next;
}
return index2;
}
}
return NULL;
}
};
总结
- 链表的种类主要为：单链表，双链表，循环链表
- 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
- 链表是如何进行增删改查的。
- 数组和链表在不同场景下的性能分析。
链表的虚拟头节点
虚拟头节点的设置是增删改查中十分重要的方法，通过设置虚拟头节点，链表在进行操作时可以不用区分进行头节点和非头节点的操作，使更加方便
ListNode* dummyNode=new ListNode(0);
dummyNode->next=head;
链表的基本操作
这是练习链表基础操作的非常好的一道题目，考察了：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点的数值
可以说把这道题目做了，链表基本操作就OK了，再也不用担心链表增删改查整不明白了。
反转链表
反转链表是十分高频的考点。先学透迭代法，然后再看递归法，因为递归法比较绕，如果迭代还写不明白，递归基本也写不明白了。
可以先通过迭代法，彻底弄清楚链表反转的过程！