代码随想录二刷Day4

今日任务

24.两两交换链表中的节点
19.删除链表的倒数第N个结点
面试题 02.07. 链表相交
142.环形链表II
语言：C++

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

链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

/*** 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) {if(head == nullptr || head->next == nullptr) return head;ListNode* dummyHead = new ListNode(0, head);ListNode* pre = dummyHead;ListNode* cur = head;ListNode* next = head->next;while(next != nullptr){pre->next = next;ListNode* tmp = next->next;next->next = cur;cur->next = tmp;pre = cur;cur = cur->next;if(cur != nullptr) next = cur->next;else next = nullptr;}head = dummyHead->next;delete dummyHead;return head;}
};

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

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

/*** 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, head);ListNode* slow = dummyHead, *fast = dummyHead;for(int i = 0; i < n; i++){fast = fast->next;}while(fast->next != nullptr){slow = slow->next;fast = fast->next;}ListNode* node = slow->next;slow->next = slow->next->next;delete node;head = dummyHead->next;delete dummyHead;return head;}
};

面试题 02.07. 链表相交

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

/*** 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) {if(headA == nullptr || headB == nullptr) return nullptr;ListNode* curA = headA;ListNode* curB = headB;while(curA != curB){if(curA == nullptr) curA = headB;else if(curB == nullptr) curB = headA;else{curA = curA->next;curB = curB->next;}}return curA;}
};

142. 环形链表II

链接：https://leetcode.cn/problems/linked-list-cycle-ii/
一些还没掌握太好的问题：
1.为什么快慢指针会在入环第一圈内就相遇？
2.如何确认环入口的位置，为什么可以这样确认？

/*** 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* slow = head, *fast = head;while(fast != nullptr && fast->next != nullptr){slow = slow->next;fast = fast->next->next;if(slow == fast){slow = head;while(slow != fast){slow = slow->next;fast = fast->next;}return fast;}}return nullptr;}
};