文章目录一、环形链表LC141问题描述解题思路代码实现二、环形链表 IILC142问题描述解题思路代码实现三、链表的回文结构OR36问题描述解题思路代码实现四、相交链表LC160问题描述解题思路代码实现一、环形链表LC141环形链表问题描述解题思路初始化快指针fast和慢指针slow都指向头节点head。在循环中快指针每次移动两步慢指针每次移动一步。若快慢指针相遇说明链表存在环返回true若快指针走到末尾fast或fast.next为null说明链表无环返回false。代码实现publicclassSolution{publicbooleanhasCycle(ListNodehead){ListNodefasthead;ListNodeslowhead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;if(slowfast){returntrue;}}returnfalse;}}二、环形链表 IILC142环形链表II问题描述解题思路首先用快慢指针法判断链表是否有环若快慢指针相遇说明有环。若有环假设起点到环起点距离为X环的距离为C相遇点到环起点距离为Y因为快指针速度为慢指针2倍所以到相遇快指针路程也是慢指针的2倍经过计算得到X Y。将慢指针重新指向头节点然后快慢指针每次都移动一步当它们再次相遇时相遇节点就是入环的第一个节点。代码实现publicclassSolution{publicListNodedetectCycle(ListNodehead){ListNodefasthead;ListNodeslowhead;// 判断是否有环while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;if(slowfast){break;}}// 无环情况if(fastnull||fast.nextnull){returnnull;}// 找入环第一个节点slowhead;while(slow!fast){fastfast.next;slowslow.next;}returnslow;}}三、链表的回文结构OR36链表的回文结构问题描述解题思路用快慢指针找到链表的中间节点。反转中间节点之后的链表部分。从原来链表的头和尾依次比较节点值是否相等若都相等则为回文链表。代码实现publicclassSolution{publicbooleanchkPalindrome(ListNodeA){if(Anull||A.nextnull){returntrue;}ListNodeslowA;ListNodefastA;// 找中间节点while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}// 反转后半部分链表ListNodecurslow.next;ListNodecurNext;while(cur!null){curNextcur.next;cur.nextslow;slowcur;curcurNext;}// 比较原链表前半部分和反转后的后半部分ListNodefirstA;while(first!slow){if(first.val!slow.val){returnfalse;}// 处理偶数长度链表的终止情况if(first.nextslow){returntrue;}firstfirst.next;slowslow.next;}returntrue;}}注意反转后半个列表后slow就在原列表尾部所以由first从前往后slow从后往前遍历列表奇数个节点当slow.val first.val即为遍历完成偶数个节点不可以直接按照奇数个的情况来判断因为会出现first和slow互换的情况。当first.nextslow即遍历完成四、相交链表LC160相交链表问题描述解题思路分别计算两个链表的长度lenA和lenB。让较长的链表先移动长度差的步数使得两个链表剩余部分长度相同。然后同时移动两个链表的指针若指针相遇则相遇节点为相交起始节点若遍历结束都未相遇则无相交节点。代码实现publicclassSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){if(headAnull||headBnull){returnnull;}ListNodeplheadA;ListNodepsheadB;intlenA0;intlenB0;while(pl!null){lenA;plpl.next;}while(ps!null){lenB;psps.next;}intlenlenA-lenB;plheadA;psheadB;if(len0){len-len;plheadB;psheadA;}for(inti0;ilen;i){plpl.next;}while(ps!pl){psps.next;plpl.next;}returnpl;}}