24. 两两交换链表中的节点
题目链接：两两交换链表中的节点
视频讲解：帮你把链表细节学清楚！
首先还是要学会使用虚拟头节点，链表中需要操作某个节点，就要定位到此节点的前一个节点。这题需要理清节点交换的的顺序以及循环终止条件。
节点交换的过程：
（步骤二进行完后，2下一个节点是1，但1的下一个节点还是2，所以1的下下节点不再是3了，故要提前储存好3）
学习总结
1、引入虚拟头结点方便操作真实的头结点；
2、在节点交换过程中，节点会改变，如果之后需要用到该节点，则需要先把该节点保存入一个临时变量；
3、确定好while循环的终止条件，链表长度为偶数，cur指针会遍历到最后一个节点，终止条件是cur->next = nullptr；若为奇数，cur会遍历到倒数第二节点,终止条件为cur->next->next = nullptr；且while中cur->next != nullptr && cur->next->next != nullptr的顺序不能颠倒，如果写成 cur->next->next != nullptr && cur->next != nullptr，就会先对cur->next->next进行判断，当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) {}
* };
*/
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dum = new ListNode(0);
dum -> next = head;
ListNode* cur = dum;
ListNode* tmp;
ListNode* tmp1;
while (cur->next != nullptr && cur->next->next != nullptr)
{
tmp = cur->next;
tmp1 = cur->next->next->next;
cur->next = cur->next->next; //此时cur->next的值变了，之后要用到变之前的值就要提前存好tmp
cur->next->next = tmp;
cur->next->next->next = tmp1; // cur->next->next->next也要提前存好
cur = cur->next->next;
}
return dum->next;
}
};
19.删除链表的倒数第N个节点
题目链接：删除链表的倒数第N个节点
视频讲解：链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点_哔哩哔哩_bilibili
这道题是对双指针的灵活运用，怎么通过双指针找到第N个节点，当然虚拟节点也不能忘。
双指针的走法：
1、首先快、慢指针都指向虚拟头结点；
2、先让快指针走N步，然后快、慢指针同时向后遍历，直到快指针指向空（就是尾节点的下一个），此时，慢指针就在倒数第N个节点；
3、要对一个节点操作就需要直到其前一个节点，所以慢指针就要指向倒数第N个节点的前一个，那么在第2步时就需要让快指针先走的步数多一步（N+1步），这样，共同向后遍历后慢指针就指向了前一个节点。
需要注意的点：在判断fast走N+1步终止条件时，应该先让fast直接走N+1步
n++;
while(n-- && fast != nullptr)
{
fast = fast->next;
}
不能让fast走N步后，再让fast指向其下一个节点。因为当N大于链表的长度时，fast走N步后就为空了，不能再对其操作了。
//错误写法
while(n-- && fast != nullptr)
{
fast = fast->next;
}
fast = fast->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) {}
* };
*/
//时间复杂度: O(n)
//空间复杂度: O(1)
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dum = new ListNode(0);
dum->next = head;
ListNode* fast = dum;
ListNode* slow = dum;
n++;
while(n-- && fast != nullptr)
{
fast = fast->next;
}
while(fast != nullptr)
{
fast = fast->next;
slow = slow->next;
}
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
return dum->next;
}
};
面试题 02.07. 链表相交
题目链接：链表相交
此题在于让链表末尾对齐，才方便找到两链表合一的交点。
方法：
1、定位两个链表的头结点
2、求出两个链表的长度，并求出其差值，让两个链表末尾对齐，并让两个指针位置对齐
3、两个指针同时向后遍历，直到他们相等（注意，是指针相等，不是值相等），没有相等的返回NULL；
学习总结：
1、求完链表长度后要把临时指针cur重新指向头结点；
2、把链表的较长或较短的那个固定住，明确知道lenA和lenB哪个是长的，哪个是短的，减少之后进行讨论；
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//时间复杂度：O(n + m)
//空间复杂度：O(1)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while (curA != NULL) // 先求两链表的长度
{
curA = curA->next;
lenA++;
}
while (curB != NULL)
{
curB = curB->next;
lenB++;
}
curA = headA;
curB = headB; // 求完链表长度，cur的位置变了，让他们重新指向头结点
if(lenA < lenB) // 保持lenA是最长的，之后可以减少讨论
{
swap(lenA, lenB);
swap(curA, curB);
}
// 求两链表的长度差
int len = lenA - lenB;
// 让两个链表的末尾对齐后，curA和curB在同一位置
while (len--)
{
curA = curA->next;
}
// 开始同时向后遍历
while(curA != NULL)
{
if (curA == curB)
return curA;
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
142.环形链表II
题目链接：环形链表II
视频讲解：把环形链表讲清楚
此题用到双指针，一快一慢。主要是要理清楚快慢指针的运动过程。
方法：
1、判断有环
分别定义 fast 和 slow 两快慢指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果两个指针在中途相遇就说明有环。
首先可以确定如果两个指针相遇肯定是在环中相遇，那么为什么一定会相遇呢？fast指针一次移两步，slow指针一次移一步，fast比slow先进入环，当都进入环中后，fast就在一步一步的追slow,所以就一定会相遇（一个移两步，一个移一步所以就差一步，即fast不会把slow跳过去的）。
2、找到环的入口
首先先定义三个节点数，头结点到入口为x，入口到相遇点为y，相遇点再到入口为z
相遇时slow走的节点数为 x + y，fast有可能绕了几圈才与slow相遇，fast走的节点数为 x + y + n(y + z)，其中 n 为fast绕的圈数。那么从出发到相遇是相同的时间两个指针走的节点数满足 2(x + y) = x + y + n(y + z)，相同时间fast走的节点数是slow的两倍。
两边消去x + y后得：x + y = n(y + z)
我们想要知道环形的入口节点，所以要得到 x 为多少，先将上式移项后得：x = n(y + z) - y，这时候x与-y有关，但我们不好定位一个负数，再转换一下则有： x = (n - 1)(y + z) + z，这样就找到x和z的关系，他们相差n-1圈，fast要和slow相遇jiu至少比slow多走一圈，所以n>=1。得到了这个关系，我们可以重新定义两个节点，idx1指向头结点，idx2指向相遇的节点。再让idx1和idx2同时出发开始往后遍历，当两个指针相遇（相等）时就是环形入口点。当然，idx2可能转几圈才会和idx相遇（n>1的情况）。
为什么fast和slow第一次在环中相遇，slow的步数是 x + y 而不是x + y + n(y + z)？
fast一定比slow先进入环，由上图可以看出，如果slow和fast同时从入环口进入环，那么slow转一圈，fast是转了两圈它们才相遇，也满足了他们在slow的第一圈就相遇了。但实际上两个指针的起始点不一定就是入环口（可能在入环口前面），所以当slow到达入环口时fast可能已经在环中了，就是接下来这种情况：
当fast到达入环口3时走了n + k 个节点，slow相应就走了(n + k) / 2 个节点。k是小于n的，(n + k) / 2就也小于n了，所以fast比slow先到达入环口3，那么他们在slow的n + k) / 2 个节点中肯定相遇了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) // fast一次要走两步，所以要判断下一个节点是否为空
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
auto idx1 = fast;
auto idx2 = head;
while(idx1 != idx2)
{
idx1 = idx1->next;
idx2 = idx2->next;
}
return idx1;
}
}
return NULL;
}
};
文章来源
发表评论