代码随想录打卡第四天

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* star new ListNode(0); star-next head; ListNode* cur star; while(cur-next ! nullptr cur-next-next ! nullptr){ ListNode* temp cur-next; cur-next temp-next; temp-next cur-next-next; cur-next-next temp; cur temp; } return star-next; } };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* star new ListNode(0); star-next head; ListNode* flag star; ListNode* cur star; while(n-- flag-next ! nullptr){ flag flag-next; } while(flag-next ! nullptr){ flag flag-next; cur cur-next; } ListNode* temp cur-next; cur-next temp-next; delete temp; ListNode* newhead star-next; delete star; return newhead; } };面试题 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* starA new ListNode(0); starA-next headA; ListNode* flagA starA; ListNode* starB new ListNode(0); starB-next headB; ListNode* flagB starB; int sizeA 0; int sizeB 0; while(flagA-next ! NULL){ flagA flagA-next; sizeA; } while(flagB-next ! NULL){ flagB flagB-next; sizeB; } if(flagA ! flagB) return NULL; flagA starA; flagB starB; if(sizeA sizeB){ int size sizeA - sizeB; while(size--){ flagA flagA-next; } }else if(sizeA sizeB){ int size sizeB - sizeA; while(size--){ flagB flagB-next; } } ListNode* flag new ListNode(0); while(flagA ! NULL flagB ! NULL){ if(flagA flagB){ flag flagA; return flag; } flagA flagA-next; flagB flagB-next; } return flag; } };142 环形链表II1.判断是否是环形链表2.定位入环点3.处理细节无环情况如何脱离4.处理细节空指针特殊情况/** * 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; if(fast NULL || fast-next NULL) return NULL; fast fast-next-next; slow slow-next; while(fast ! NULL fast-next ! NULL fast ! slow){ fast fast-next-next; slow slow-next; } if(fast NULL || fast-next NULL) return NULL; slow head; while(slow ! fast){ fast fast-next; slow slow-next; } return slow; } };