力扣算法刷题-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个节点当快指针移动到结尾时慢指针指向的就是需要删除的节点。需要注意在实际编写时可以让快指针先跑n1步这样慢指针会指向需要删除的节点的前一个节点便于删除操作。文章详解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看是否相等。On2复杂度。想到特殊情况若是两个链表长度相等便可让两个指针同步进行移动一定会同时到达相交节点进而想到相交节点位置出现一定在短的之后。先让长的链表和短的对齐。进而同时移动。文章详解面试题 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) * (yz) 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; } };