【力扣hoot100----链表】

1.相交链表给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回null。先将链表从前往后遍历遇到空就指向另一个链表的头节点。因为xz)y(yz)x所以如果两条链表交点一定会同时到达那个交点的地方如果没有交点那就全部到达NULL。可以自己找一个例子试一下循环结束的条件就是PQ这对这两种情况都适用。最后返回NULL/交点总结当我们无路可走时试着走彼此的路. 如果到最后我找不到你那么你也找不到我我们没有缘分了//当我们无路可走时试着走彼此的路. 如果到最后我找不到你那么你也找不到我我们没有缘分了 class Solution { public: ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* p headA; ListNode* q headB; while (p ! q) { p p ? p-next : headB; q q ? q-next : headA; } return p; } };2.链表反转我的思路是对链表进行原地箭头的反转定义三个指针prev指向curr前面的节点next指向curr后面的节点curr指向当前节点比较简单直接看代码吧class Solution { public: ListNode* reverseList(ListNode* head) { if(headnullptr||head-nextnullptr){ return head; } ListNode*currhead; ListNode*prevNULL; while(curr!NULL){ ListNode*nextcurr-next; curr-nextprev; prevcurr; currnext; } return prev; } };3.回文链表回文链表是指一个链表其节点值的序列从前往后读和从后往前读是一样的。回文链表具有对称性就像回文字符串一样。示例1 - 2 - 3 - 2 - 1 (奇数长度对称)1 - 2 - 2 - 1 (偶数长度对称)1 - 1 (两个相同元素)1 (单个元素总是回文)空链表 (空链表被认为是回文)思路这里采用迭代法递归也可以有时间再研究首先要找到链表的中间节点图片来源灵茶山艾府将中间到后面的链表进行反转。两个链表进行比对判断是否回文代码class Solution { // 找到中间节点 ListNode* middlenode(ListNode* head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; } // 反转中间到后面的 ListNode* reversenode(ListNode* head) { ListNode *curr head, *prev nullptr; while (curr) { ListNode* next curr-next; curr-next prev; prev curr; curr next; } return prev; } public: bool isPalindrome(ListNode* head) { ListNode* mid middlenode(head); ListNode* head2 reversenode(mid);//这里注意不能传入整个链表只反转中间往后的。 while (head2) { if (head-val head2-val) { head head-next; head2 head2-next; } else { return false; // 不是回文 } } return true; } };4.环形链表判断一个链表里面是否有环思路快慢指针fast slow都从head出发如果他们相遇了说明链表里面存在环注意相遇点不一定是入环节点相遇了只代表有环/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { ListNode*fasthead; ListNode*slowhead; while(fastfast-next){ slowslow-next; fastfast-next-next; if(fastslow){ return true; } } return false; } };哈希表解决用哈希表存储已经遍历过的节点如果下一次的节点在哈希表里面存过了说明有环。unordered_set无序集合常用方法size()和empty():用于获取大小和集合是否为空find():用于查找键insert()和erase():用于插入和删除元素count():计算在无序集合容器中特定元素的出现次数基于无序集合的实际问题已知一个整数数组要找出其中的所有重复项。class Solution { public: bool hasCycle(ListNode *head) { unordered_setListNode* seen; while (head ! nullptr) { if (seen.count(head)) { return true; } seen.insert(head); head head-next; } return false; } };5.环形链表Ⅱ给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。算法步骤Floyd判圈法判断是否有环快慢指针若快指针为null则无环返回null。找到相遇点快慢指针第一次相遇的位置。找入环点将慢指针移回头节点快指针留在相遇点两者每次各走一步再次相遇处即为入环点。从链表头出发的指针和从相遇点出发的指针再次相遇的那个节点这个节点才是入环点。/** * 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* fasthead; ListNode* slowhead; while(fastfast-next){ slowslow-next; fastfast-next-next; if(slowfast){ while(slow!head){ slowslow-next; headhead-next; } return slow; } } return NULL; } };持续更新中。。。