526互联

算法学习Day4两两交换，链表相交，环形链表

发布时间 2023-12-16 20:13:46作者: HQWQF

Day4两两交换，链表相交，环形链表

By HQWQF 2023/12/16

笔记

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解法：迭代法

迭代法使用了虚拟头节点的技巧，

迭代法代码

class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head;
ListNode* cur = dummyHead;//cur为指向需要反转的元素对的节点
while(cur->next != nullptr &&cur->next->next != nullptr )
{
//临时变量保存原始的信息
ListNode* tmp1 = cur->next; //需要的反转元素1
ListNode* tmp2 = cur->next->next; //需要的反转元素2
ListNode* nextcur = cur->next->next->next; //需要的反转元素2对指向的节点
//保存下来的原始链表的局部： cur ->tmp1 ->tmp2 ->nextcur

cur->next = tmp2;
tmp2 ->next = tmp1;
tmp1 ->next = nextcur;
cur = tmp1;
}
ListNode* result = dummyHead->next;
delete dummyHead;
return result;
}
};

注释：

  • 在局部调整链表时可以多用临时变量进行保存，这样不容易出错，然后画链表调整的图示，一条箭头表示行代码。

19.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解法：快慢指针

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

实际算法中，由于可能删除头结点，我们要让fast移动n+1步，删掉slow→next。

快慢指针代码

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
//使用虚拟头结点，这样方便处理删除实际头结点
ListNode* dh = new ListNode();
dh ->next = head;
ListNode* fastindex = dh;
ListNode* slowindex = dh;
for(int i = 0;i<n;i++)
{
fastindex = fastindex->next;
}
fastindex = fastindex->next;// fast再提前走一步，因为需要让slow指向删除节点的上一个节点
while(fastindex)
{
fastindex = fastindex ->next;
slowindex = slowindex ->next;
}
ListNode* del = slowindex->next;
slowindex->next = slowindex->next->next;
ListNode* res = dh->next;
delete del;//删除节点要释放
delete dh;
return res;
}
};

面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交 ：

如果使用存储这题就很简单了，但是这里用的是空间复杂度O(1)的算法

解法：快慢指针

两个指针分别指向两个表头，获取两个链表的长，长的那个指针向前移动比另一个链表长的长度，后两指针同步向前移动的同时检测指针是否相等，相等即为交点，移动完都没检测到相等就是没有交点

快慢指针代码

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode * curA = headA;
ListNode * curB = headB;
int lenA = getListSize(headA);
int lenB = getListSize(headB);
int offset;
if(lenA > lenB)
{
offset = lenA-lenB;
for(int i = 0;i < offset;i++)
{
curA = curA -> next;
}
while(curA)
{
if(curA!=curB)
{
curA = curA -> next;
curB = curB -> next;
}else
{
return curA;
}
}
}else
{
offset = lenB-lenA;
for(int i = 0;i < offset;i++)
{
curB = curB -> next;
}
while(curB)
{
if(curA!=curB)
{
curA = curA -> next;
curB = curB -> next;
}else
{
return curB;
}
}
}
return NULL;
}
int getListSize(ListNode *head)
{
ListNode* cur = head;
int len = 0;
while(cur)
{
cur = cur->next;
len++;
}
return len;
}

};

实际上我们可以使用swap 来交换指针变量的值，这样我们就不用分别处理哪个表更长的情况了。

快慢指针代码，使用swap

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;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap--) {
curA = curA->next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != NULL) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};

142.环形链表II

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

解法：快慢指针

检测是否有环：定义一对快慢指针，慢指针一次循环走一位，快指针一次循环走两位，如果指针最终相遇则有环，如果其中一个指针碰到NULL则无环。（以相对速度的视角看，如果有环两个指针必定相遇）

获取环入口：获得相遇节点后，让一个指针从头出发，一个指针在相遇节点出发，两个指针相遇的位置就是入口，推导如下：

相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

为什么slow指针走过的节点数为: x + y，也就是说在slow走完一圈之前两个指针就会相遇？

因为无论slow指针进入环时，fast指针在什么位置，由于fast指针的速度是slow指针的两倍，在slow指针走完一圈之前fast指针都会追上

由于slow指针走过的节点数 * 2= fast指针走过的节点数，所以x + y*2 =x + y + n (y + z)可以简化为

为如下公式：x = (n - 1) (y + z) + z ，可以看出头节点到入口的距离一定等于相遇节点到入口的距离加上若干圈的长度。

代码

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;
}
};