LeetCode 24. 两两交换链表中的节点
题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）
视频链接：帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点_哔哩哔哩_bilibili
思路
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
这种题建议画图，不然的话很多指针容易乱，最好用虚拟头结点的方式，这样就不用再进行单独处理。很多人这种题的过程容易写错，就像这道题，正确的过程如下图所示：
先让cur指向虚拟头节点，然后进行以下操作
代码实现：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* temp = cur->next;
ListNode* temp1 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = temp;
cur->next->next->next = temp1;
cur = cur->next->next;
}
return dummyHead->next;
}
};·时间复杂度：O（n）
·空间复杂度：O（1）
LeetCode 19.删除链表的倒数第N个节点
题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
视频链接：链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点_哔哩哔哩_bilibili
思路
依旧是用虚拟头结点的方法，运用双指针，这里需要注意的是，想要删除倒数第N个节点，慢指针必须指向被删除节点的前一个结点上，如图所示：
代码实现：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* fast = dummyhead;
ListNode* slow = dummyhead;
while(n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next;
while(fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummyhead->next;
}
};·时间复杂度：O（n）
·空间复杂度：O（1）
LeetCode 160.链表相交
题目链接：160. 相交链表 - 力扣（LeetCode）
思路
定义两个指针，一个指向第一个链表的头节点，另一个指向第二个链表的头节点，先分别求出两个链表各自的长度，再求出差值，然后再一个一个向后移动，直到两个指针相等，交点就找到了，过程如图所示：
代码实现：
代码实现：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA =0,lenB = 0;
while(curA != NULL) {
lenA++;
curA = curA->next;
}
while(curB != NULL) {
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
if (lenB > lenA) {
swap (lenA,lenB);
swap (curA,curB);
}
int cha = lenA - lenB;
while(cha) {
curA = curA->next;
cha--;
}
while(curA != NULL) {
if(curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};·时间复杂度：O(n + m)
·空间复杂度：O(1）文章来源地址https://www.toymoban.com/news/detail-602051.html
LeetCode 142.环形链表
题目链接：142. 环形链表 II - 力扣（LeetCode）
视频链接：把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？ LeetCode：142.环形链表II_哔哩哔哩_bilibili
思路
看到这道题，首先要判断所给的链表是否是环，如果是环，那么入口在哪。这道题依旧使用快慢指针的方法，让快指针每次走两步，慢指针每次走一步，如果他俩在途中相遇，就证明这个链表有环。过程如图所示：
链表有环证明出来以后，就要思考环的入口在哪。
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：
所以相遇时，慢指针走过的节点数：x+y 快指针走过的节点数：x+y+n(y+z)。因为快指针每次走两步，慢指针每次走一步，所以(x+y)*2=x+y+n(y+z)，因为要找入口距离，所以将x放左边，经过一顿神化简得x=(n-1)(y+z)+z(n一定是>=1的）
令n=1，公式x=z，这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
如图所示：
代码实现：
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(slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
while(index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
};·时间复杂度：O(n)文章来源：https://www.toymoban.com/news/detail-602051.html
·空间复杂度：O(1）
到了这里，关于Day4|LeetCode 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、160.链表相交、142.环形链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
