代码随想录算法训练营Day.4 | 两两交换链表中的节点删除链表的倒数第 N 个结点链表相交环形链表Ⅱ

前段时间比较忙，去长沙参加比赛用了两天，然后准备组会两天，累了累了，这就速度补

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

虽然是middle但是就是对链表的一个理解，两两交换需要记录三个节点才可以完成，同时需要一个虚拟头节点dumyNode。代码如下：

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(!head) return head;ListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* preNode = dummyNode;ListNode* midNode = head;ListNode* nextNode = midNode->next? midNode->next:nullptr;while(nextNode != nullptr){preNode->next = nextNode;midNode->next = nextNode->next;nextNode->next = midNode;// 更新preNode = midNode;midNode = preNode->next;nextNode = midNode? midNode->next:nullptr;}return dummyNode->next;}
};

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

很明显，在我无法后退的情况下，要得到第N个节点，就需要快慢指针间隔N，同时还需要考虑到删除头节点的情况，所以要引入虚拟头节点。代码如下：

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if(head->next == nullptr) return nullptr;ListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* slowNode = dummyNode;ListNode* fastNode = dummyNode;int length = 0;while(fastNode != nullptr){fastNode = fastNode->next;if(length != n+1)length ++;elseslowNode = slowNode->next;}ListNode* aimNode = slowNode->next;if(n == 1) slowNode->next = nullptr;else{slowNode->next = aimNode->next;aimNode->next = nullptr;}return dummyNode->next;}
};

面试题02.07.链表相交

我的思考是，先找到两个链表长度差，然后两侧同步前进，第一个相同的节点就是初始交点，但是代码实现的比较烂。代码如下：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB) return nullptr;// find tailListNode* findA = headA;ListNode* findB = headB;if(findA == findB) return findA;int skipA{0}, skipB{0};bool isFind = false;while(findA->next != nullptr || findB->next != nullptr){if(findA->next != nullptr) findA = findA->next;else  skipA ++;if(findB->next != nullptr) findB = findB->next;else  skipB ++;if(findA == findB) {isFind = true; break;}}if(!isFind) return nullptr;findA = headA;findB = headB;if(skipA > 0){while(skipA > 0){findB = findB->next;skipA --;}}else{while(skipB > 0){findA = findA->next;skipB --;}}while(findA != nullptr || findB != nullptr){if(findA == findB) return findA;findA = findA->next;findB = findB->next;}return findA;}
};

看了下随想录的代码，结果想法和我一样，有点离谱的就是LeetCode另一个方法是哈希集合，我属实是被限制住了，这道题的easy方法就在这里，代码如下：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> visited;ListNode *temp = headA;while (temp != nullptr) {visited.insert(temp);temp = temp->next;}temp = headB;while (temp != nullptr) {if (visited.count(temp)) {return temp;}temp = temp->next;}return nullptr;}
};