24.两两交换链表中的结点
思路：
- 设置一个虚拟头结点，设置一个当前结点等于虚拟头结点，进行移动操作。指向两两交换的第二个结点，第二结点的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) {
ListNode* dummynode=new ListNode(0);//设置虚拟头结点
dummynode->next=head;
ListNode* cur = dummynode;//设置当前执行结点
while(cur->next!=nullptr&&cur->next->next!=nullptr)
{
ListNode* temp1 = cur->next;//temp1储存原链表的第一个结点
ListNode* temp2 = cur->next->next->next;//temp2储存原链表的第二个结点
cur->next=cur->next->next;//将第二个结点变成第一个结点
cur->next->next=temp1;//将第二个节点连接原链表的第一个结点
cur->next->next->next=temp2;//把第三个结点连接起来
cur=cur->next->next;//移动当前结点
}
ListNode* newhead=dummynode->next;
delete dummynode;
return newhead;
}
};
删除链表的倒数第n个结点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
思路：
- 设置两个指针，一个快指针，一个慢指针，快指针先移动n步，再移动1步（确保慢指针能移动到目标结点的上一个，方便进行删除操作）
- 同时移动快慢指针，直到快指针指向空
- 慢指针对结点进行删除操作
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummynode=new ListNode(0);
dummynode->next=head;
ListNode* fast=dummynode;//设置快指针
ListNode* slow=dummynode;//设置慢指针
while(n--&&fast!=NULL)//快指针先移动n步
{
fast=fast->next;
}
fast=fast->next;//多移动一步，方便慢指针进行移除操作
while(fast!=NULL)
{
fast=fast->next;
slow=slow->next;
}
ListNode* temp=slow->next;
slow->next=slow->next->next;
delete temp;
head=dummynode->next;
delete dummynode;
return head;
}
};
02.07.链表相交
面试题 02.07. 链表相交 - 力扣（LeetCode）
思路：
- 求链表的交点就是求链表指针相同，首先求出两个链表的长度
- 求出链表A和链表B的差值s
- 将长的那条链表的头结点移动s个位置
- 同时移动链表A和链表B的指针，直到两个指针相等，相等的指针就是两个链表的交点
- 为了保证移动便利，始终坚持A链表是最长的那个链表，使用C++的标准库函数swap()实现两个链表值的交换。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA=headA;
ListNode* curB=headB;
int lenA=0;
int lenB=0;
while(curA!=NULL)//判断其是否为空指针
{
lenA++;
curA=curA->next;
}
while(curB!=NULL)
{
lenB++;
curB=curB->next;
}
curA=headA;//前面对指针进行了移动的操作，所以要重新返回头结点
curB=headB;
if(lenA<lenB)
{
swap(curA,curB);//swap交换变量的值
swap(lenA,lenB);
}
int s = lenA-lenB;//求出两条链表的差值
while(s--)
{
curA=curA->next;
}
while(curA!=NULL)
{
if(curA==curB)
{
return curA;
}
curA=curA->next;
curB=curB->next;
}
return NULL;
}
};
142.环形链表
142. 环形链表 II - 力扣（LeetCode）
思路：
解决这个问题首先要考虑两种情况
- 链表是否有环
- 链表如果有环，那么环的入口在哪里
链表是否有环
要判断链表是否有环:
- 设定两个指针，快指针移动两步，慢指针移动一步
- 入环后两个指针就在环内移动
- 如果链表有环，那么两个指针一定会相遇
- 两个指针在链表中相遇证明链表有环，没有相遇，证明链表无环。
环的入口问题
这是一个数学问题：
设头结点到入口的距离为x,r入口到相遇点的距离为y,相遇点到入口的距离为z.
那么慢指针到相遇点的走过的结点数就是x+y;
快指针走过的节点数就是x+y+n(y+z);
由于快指针走过的结点数是慢指针的两倍，所以他们相遇时2（x+y）=x+y+n(y+z)；
两边同时消掉一个x+y；
得到x+y=n(y+z)；
作一个变形的x=(n-1)(y+z)+z；
当快指针走了第一圈时，快慢指针就能相遇，故n=1时，x=z;
此时，从相遇点头结点同时开始移动指针，当指针相遇时，就是环形链表的入口。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
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;//快指针移动两步
if(fast==slow)//找到环形链表的相遇点
{
ListNode* index1=fast;
ListNode* index2=head;
while(index1!=index2)//从相遇点和头结点开始移动，直到两个指针相等
{
index1=index1->next;
index2=index2->next;
}
return index2;
}
}
return NULL;
}
};
