系列文章目录
代码随想录算法训练营第四天：代码随想录|LeetCode24. 两两交换链表中的节点 LeetCode19.删除链表的倒数第N个节点 面试题02.07. 链表相交 LeetC142.环形链表
文章目录
前言
代码随想录|LeetCode24. 两两交换链表中的节点 LeetCode19.删除链表的倒数第N个节点 面试题02.07. 链表相交 LeetC142.环形链表II
文章链接
一、LeetCode24. 两两交换链表中的节点
1、题目链接
2、题解
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* cur = head;
if (cur == NULL)
return head;
if (cur->next == NULL)
return head;
if (cur->next->next == NULL) {
ListNode* t1 = head;
ListNode* t2 = head->next;
ListNode* t3 = head->next->next;
head = t2;
head->next = t1;
head->next->next = t3;
cur = t1;
return head;
}
while (cur->next != NULL && cur->next->next != NULL) {
if (cur == head) {
ListNode* t1 = head;
ListNode* t2 = head->next;
ListNode* t3 = head->next->next;
head = t2;
head->next = t1;
head->next->next = t3;
cur = t1;
} else {
ListNode* temp = cur->next;
ListNode* k = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = temp;
cur->next->next->next = k;
cur = cur->next->next;
}
}
return head;
}
};
二、LeetCode19.删除链表的倒数第N个节点
1.题目链接
LeetCode19.删除链表的倒数第N个节点
这道题定位是要点
2.暴力法
（1）思路：
先从头到尾遍历，求出长度，再用长度和n定位
（2）C语言题解
int getlen(struct ListNode* head)
{
int res=0;
if(head==NULL)return res;
struct ListNode* p=head;
while(p!=NULL)
{
res++;
p=p->next;
}
return res;
}
void delete(struct ListNode * head,int m)
{
struct ListNode* now=head;
struct ListNode* pre=(struct ListNode*)malloc(sizeof(struct ListNode));
pre->next=head;
int i=1;
for(i;i<m;i++)
{
pre=now;
now=now->next;
}
pre->next=now->next;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
if(head==NULL)return head;
int l=getlen(head);
struct ListNode* now=head;
struct ListNode* pre=(struct ListNode*)malloc(sizeof(struct ListNode));
pre->next=head;
if(l==n)
{
head=head->next;
}
for(int i=1;i<l-n+1;i++)
{
pre=now;
now=now->next;
}
pre->next=now->next;
return head;
}
该处使用的url网络请求的数据。
3、仅遍历一次的做法：快慢指针
（神奇的是暴力法的用时更短）
（1）思路
1）既然要删除倒数第n个节点，那么我们需要把慢指针p放在倒数第n个节点的前一个节点处（n+1），那么如何确定何时到达这个位置呢
2）我们再用一个快指针，当快指针为最后一个节点时，快指针应当领先于慢指针n个节点
3）所以一开始让快指针先走n个节点，再让两个指针同时前进，直到快指针的下一个节点为空，即快指针到达最后一个节点
4）这时候慢指针为倒数n+1个节点
（2）题解
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy= new ListNode(0,head);
ListNode* p=dummy;
ListNode* end=dummy;
for(int i=0;i<n;i++)
{
if(end->next==NULL)break;
end=end->next;
}
while(end!=NULL && end->next!=NULL)
{
end=end->next;
p=p->next;
}
p->next=p->next->next;
return dummy->next;
}
};
三、面试题02.07. 链表相交
1、题目链接
2、思路
（1）这里注意链表相交不是值相等，而是地址相等
（2）如果链表相交，那么从相交点以后的长度也相等。链表的终点都是NULL，在思考的时候，可以将链表尾部对齐
（3）如果两个链表长度不同，那么长的链表多出来的部分是不可能相交的，所以先把长的链表遍历的指针移动到和短链表平齐的位置
（4）接下来同时移动两个指针，如果地址相同，则为相交点，返回此时的指针
3、题解
class Solution {
public:
int len(ListNode* head) {
ListNode* p = head;
int ans = 0;
while (p != NULL) {
p = p->next;
ans++;
}
return ans;
}
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* ans = NULL;
ListNode* p1 = headA;
ListNode* p2 = headB;
int lenA = len(headA);
int lenB = len(headB);
if (lenA > lenB) {
int n = lenA - lenB;
for (int i = 0; i < n; i++) {
p1 = p1->next;
}
} else if (lenA < lenB) {
int n = lenB - lenA;
for (int i = 0; i < n; i++) {
p2 = p2->next;
}
}
while (p1 != NULL && p2 != NULL) {
if (p1 == p2) {
ans = p1;
break;
}
p1 = p1->next;
p2 = p2->next;
}
return ans;
}
};
四、LeetC142.环形链表II
1、题目链接
2、思路
（1）判断是否有环
快慢指针fast和slow，fast每次移动两个，slow每次移动一个
二者相遇则有环
（2）判断环的入口
再设两个指针p1,p2分别从头结点和快慢指针相遇点出发，每次移动一个，二者相遇点为入口
推导
示意图
fast和slow相遇时，假设slow第一次进入环，fast在环中多转n圈，此时fast走过的路程是x+y+n(y+z)，等于slow路程的二倍，x+y+n(y+z)=2(x+y)
所以x=z+(n-1)(y+z) （1）
在环入口处，从head出发走了x，从快慢节点相遇点出发走了z+(n-1)(y+z)【(n-1)(y+z)是转圈的路程】，由于同时出发和式（1），当p1p2二者相遇的时候是环的入口
注意：先移动，再比较是快慢指针否相等，因为快慢指针的起点都是head
3、题解
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
ListNode* pos=NULL;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
ListNode* p1 = head;
ListNode* p2 = fast;
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
pos=p1;
break;
}
}
return pos;
}
};
总结
链表部分知识点
1、链表理论知识
2、虚拟头结点的技巧
3、链表的增删改查
4、反转一个链表
5、删除倒数第N个节点
6、链表相交
7、有否环形，以及环的入口