力扣算法刷题-Day 4
24 两两交换链表节点
题目链接
24. 两两交换链表中的节点 - 力扣（LeetCode）
思路
两两交换，例如1-2-3-4 --------- 2-1-4-3,需要断开prehead和1、1和2、2和3，因此处于目标两个节点的前一个节点才能交换。加入一个虚拟头节点便于处理。若为偶数，cur的下一个节点不能为空；若为奇数，cur下一个节点的下一个节点不能为空。
文章详解
24. 两两交换链表中的节点 | 代码随想录
/** * 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* prehead = new ListNode(0, head); ListNode* cur = prehead; while (cur->next != NULL && cur->next->next != NULL) { 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; } return prehead->next; } };19 删除链表倒数第N个节点
题目链接
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
思路
直观的暴力解法，先数出倒数第n个是正数第几个；再遍历到该节点的前一个节点，删除；需要遍历两趟。
只要遍历一趟，引入双指针。我们可以设计一个快指针，先跑起来，然后慢指针与它相隔n-1个节点，当快指针移动到结尾时，慢指针指向的就是需要删除的节点。
需要注意在实际编写时，可以让快指针先跑n+1步，这样慢指针会指向需要删除的节点的前一个节点，便于删除操作。
文章详解
19.删除链表的倒数第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* prehead = new ListNode(0,head); ListNode* fast = prehead; ListNode* slow = prehead; for(int i = 0; i < n + 1; i++) { fast = fast->next; } while(fast!=NULL) //注意此处不能写fast->next!=NULL,会造成空指针异常 { fast = fast->next; slow = slow->next; } ListNode* tmp = slow->next; slow->next = slow->next->next; delete tmp; return prehead->next; } };链表相交
题目链接
面试题 02.07. 链表相交 - 力扣（LeetCode）
思路
首先想到的是暴力。对于a的每一个节点，循环一遍b看是否相等。O（n2）复杂度。
想到特殊情况若是两个链表长度相等，便可让两个指针同步进行移动，一定会同时到达相交节点；进而想到，相交节点位置出现一定在短的之后。先让长的链表和短的对齐。进而同时移动。
文章详解
面试题 02.07. 链表相交 | 代码随想录
/** * 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* tmp = headA; ListNode* tmp1 = headB; int la = 0; int lb = 0; // 统计长度 while (tmp != NULL) { tmp = tmp->next; la++; } while (tmp1 != NULL) { tmp1 = tmp1->next; lb++; } // 修正偏移 tmp = headA; tmp1 = headB; int offset = la - lb; if (offset >= 0) { while (offset--) { tmp = tmp->next; } } else { offset = 0 - offset; while (offset--) { tmp1 = tmp1->next; } } // 开始寻找 while (tmp != NULL && tmp1 != NULL) { if (tmp == tmp1) { return tmp; } tmp = tmp->next; tmp1 = tmp1->next; } return NULL; } };142 环形链表
题目链接
142. 环形链表 II - 力扣（LeetCode）
思路
首先说如何判断有环：快指针每次前进两格，慢指针每次前进一格。由于快指针相对慢指针每次前进1格，所以谈若有环，二者终会相遇。即，若二者相遇则有环。 再来说明如何判断入口。首先用数学公式推导：
快指针跑过的距离：x + n * (y + z)
慢指针：x + z
由速度关系得知：快 = 2慢
所以整理得：x = (n-1) * (y+z) + z
从相遇的位置出发一个指针p1，从最开始出发的位置出发一个指针p2，他们同时移动；
由于y + z为一圈的长度，我们分析可知，p1和p2最后相遇的地方就是目标入口节点。
文章详解
142.环形链表II | 代码随想录
/** * 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 *fast = head; ListNode *slow = head; while(fast != NULL && fast->next!=NULL &&fast->next->next!=NULL) { fast = fast->next->next; slow = slow->next; if(fast == slow) { slow = head; { while(fast!=slow) { fast = fast->next; slow = slow->next; } return slow; } } } return NULL; } }; ```