企业官网建设流程全解析

一、环形链表（LC141）

环形链表

问题描述

解题思路

• 初始化快指针fast和慢指针slow都指向头节点head。
• 在循环中，快指针每次移动两步，慢指针每次移动一步。
• 若快慢指针相遇，说明链表存在环，返回true；若快指针走到末尾（fast或fast.next为null），说明链表无环，返回false。

代码实现

publicclassSolution{publicbooleanhasCycle(ListNodehead){ListNodefast=head;ListNodeslow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(slow==fast){returntrue;}}returnfalse;}}

二、环形链表 II（LC142）

环形链表II

问题描述

解题思路

1. 首先用快慢指针法判断链表是否有环，若快慢指针相遇，说明有环。
2. 若有环，假设起点到环起点距离为X，环的距离为C，相遇点到环起点距离为Y
3. 因为快指针速度为慢指针2倍，所以到相遇，快指针路程也是慢指针的2倍，经过计算得到X == Y。
4. 将慢指针重新指向头节点，然后快慢指针每次都移动一步，当它们再次相遇时，相遇节点就是入环的第一个节点。
   

代码实现

publicclassSolution{publicListNodedetectCycle(ListNodehead){ListNodefast=head;ListNodeslow=head;// 判断是否有环while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(slow==fast){break;}}// 无环情况if(fast==null||fast.next==null){returnnull;}// 找入环第一个节点slow=head;while(slow!=fast){fast=fast.next;slow=slow.next;}returnslow;}}

三、链表的回文结构（OR36）

链表的回文结构

问题描述

解题思路

1. 用快慢指针找到链表的中间节点。

2. 反转中间节点之后的链表部分。
   

3. 从原来链表的头和尾依次比较节点值是否相等，若都相等则为回文链表。

代码实现

publicclassSolution{publicbooleanchkPalindrome(ListNodeA){if(A==null||A.next==null){returntrue;}ListNodeslow=A;ListNodefast=A;// 找中间节点while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}// 反转后半部分链表ListNodecur=slow.next;ListNodecurNext;while(cur!=null){curNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}// 比较原链表前半部分和反转后的后半部分ListNodefirst=A;while(first!=slow){if(first.val!=slow.val){returnfalse;}// 处理偶数长度链表的终止情况if(first.next==slow){returntrue;}first=first.next;slow=slow.next;}returntrue;}}

注意：
反转后半个列表后slow就在原列表尾部，所以由first从前往后，slow从后往前遍历列表

• 奇数个节点：当slow.val == first.val即为遍历完成
• 偶数个节点：不可以直接按照奇数个的情况来判断，因为会出现first和slow互换的情况。当first.next==slow即遍历完成
  

四、相交链表（LC160）

相交链表

问题描述

解题思路

1. 分别计算两个链表的长度lenA和lenB。
2. 让较长的链表先移动长度差的步数，使得两个链表剩余部分长度相同。
3. 然后同时移动两个链表的指针，若指针相遇，则相遇节点为相交起始节点；若遍历结束都未相遇，则无相交节点。

代码实现

publicclassSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){if(headA==null||headB==null){returnnull;}ListNodepl=headA;ListNodeps=headB;intlenA=0;intlenB=0;while(pl!=null){lenA++;pl=pl.next;}while(ps!=null){lenB++;ps=ps.next;}intlen=lenA-lenB;pl=headA;ps=headB;if(len<0){len=-len;pl=headB;ps=headA;}for(inti=0;i<len;i++){pl=pl.next;}while(ps!=pl){ps=ps.next;pl=pl.next;}returnpl;}}