【代码随想录37期】Day04 两两交换链表中的节点、删除链表的倒数第N个节点、链表相交、环形链表II

本文主要是介绍【代码随想录37期】Day04 两两交换链表中的节点、删除链表的倒数第N个节点、链表相交、环形链表II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

两两交换链表中的节点

/*** 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 *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *cur = dummyHead; while(cur->next&&cur->next->next){ListNode* tmp = cur->next; // 记录临时节点ListNode* tmp1 = cur->next->next->next; // 记录临时节点cur->next = cur->next->next;    // 步骤一cur->next->next = tmp;          // 步骤二cur->next->next->next = tmp1;   // 步骤三cur = cur->next->next; // cur移动两位，准备下一轮交换}return  dummyHead->next;}
};

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

注意使用虚拟头节点，可以避免对头节点的判断，防止各种复杂情况

/*** 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* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n--&&fast){fast = fast->next;}fast = fast->next;while(fast){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummyHead->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* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n--&&fast){fast = fast->next;}fast = fast->next;while(fast){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummyHead->next;}
};

if(head->next==nullptr)return nullptr;ListNode* slow = head;ListNode* fast = head;while(n--&&fast!=nullptr){fast = fast->next;}fast = fast->next;while(fast){slow = slow->next;fast = fast->next;}slow->next= slow->next->next;return head;

链表相交

代码随想录

面试题 02.07. 链表相交 - 力扣（LeetCode）

v1.0：感觉使用了虚拟头节点之后很顺利，直接模拟就可以写出来，不过就是感觉写的有点长？
/*** 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 *dummyHeadA = new ListNode(0);ListNode *dummyHeadB = new ListNode(0);int lengthA = 0, lengthB = 0;dummyHeadA->next = headA;dummyHeadB->next = headB;ListNode *lna = dummyHeadA;ListNode *lnb = dummyHeadB;while(lna){lengthA++;lna = lna->next;}while(lnb){lengthB++;lnb = lnb->next;}int steps = 0;lna = dummyHeadA;lnb = dummyHeadB;if(lengthA>=lengthB){steps = lengthA - lengthB;while(steps--){lna = lna->next;}while(lna->next!=lnb->next){lna = lna->next;lnb = lnb->next;}if(lna->next==nullptr){return nullptr;}else{return lna->next;}}else{steps = lengthB - lengthA;while(steps--){lnb = lnb->next;}while(lna->next!=lnb->next){lna = lna->next;lnb = lnb->next;}if(lna->next==nullptr){return nullptr;}else{return lna->next;}}}
};

环形链表Ⅱ

142. 环形链表 II - 力扣（LeetCode）

v1.0 这道题很巧妙，是看了随想录的讲解才做出来的
1. 判断有无环:定义快慢指针，快指针一次走两个节点，慢指针走一个，快指针追上慢指针说明有环
2. 追上时需要纸笔列下式子，此时快慢指针走过的节点数量，然后要求的是从开始节点到进入环的节点的长度
3. 具体推导可以看随想录，总之就是需要列一下式子就可以找出关系了~
/*** 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 *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *fast = head;ListNode *slow = head;ListNode *aux = head;while(fast&&fast->next){fast= fast->next->next;slow = slow->next;if(fast==slow){while(aux!=slow){slow=slow->next;aux=aux->next;}return aux;}}return nullptr;}
};