企业官网建设流程全解析

1.相交链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
注意：请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

解题思路：双指针

• A 链表独有部分长度 = a
• B 链表独有部分长度 = b
• 公共部分长度 = c

• 设置两个指针 pA 和 pB
• 让 pA 走完 A 后再走 B，当第二遍走到相交节点的时候，走过的长度为 a+c+b
• 让 pB 走完 B 后再走 A，当第二遍走到相交节点的时候，走过的长度为 b+c+a
• 也就是说两个指针在第二遍走到相交节点时的路径长度一样，此时如果两指针相等，就判定为相交节点，如果都指向空（c=0）两指针都指向末尾，此时就没有相交节点

要么两个指针每次逐步向后移动一位，直到判定为相等（此时相交节点）
第一次遍历如果其中有指针指向null，就变换为另一条的头节点
第二次便利两个同时指向null，判定为不相交
经过两次遍历后，要么都指向null，要么相交指向同一个相交节点
如果两个链表长度相同，即a=b，那第一次遍历的时候就能找到了

publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){ListNodepA=headA;ListNodepB=headB;while(pA!=pB){pA=pA==null?headB:pA.next;pB=pB==null?headA:pB.next;}returnpA;}

2.反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路：指向反转（迭代法）⭐

考虑三个指针

• pre ：已经反转好的部分
• cur ：当前正在处理的节点
• next ：提前保存 cur 后面的节点

null1→2→3→4→5→ null ↑ ↑ ↑ pre cur next

此时处理第一个节点，将1的下一个指向设置为null

null ←12→3→4→5→ null ↑ ↑ ↑ pre cur next

null ←12→3→4→5→ null ↑ ↑ ↑ pre cur next

处理完成后，原来cur的位置变为pre，原来next即变成下一个要处理的节点cur。直到处理到末尾，即next = null，此时返回当前节点为头节点

publicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurr=head;//考虑为[]的情况，此时没有next,cur为nullwhile(curr!=null){ListNodenext=curr.next;curr.next=prev;prev=curr;curr=next;}returnprev;}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

不能直接拷贝value值进行反转，这样只是修改了节点存储的数据，并没有改变节点之间的 next 指向。反转链表本质上是反转节点之间的连接关系。

解题思路：从前向后递归翻转（递归法）

从后向前处理节点，当第一次调用reverseList(1)，后续会递归到reverseList(2)、reverseList(3)，

node1 ↓[1]→[2]→[3]

到3之后，返回为null，此时开始处理reverseList(2)，此时叫 3.next=2
，2.next=null，

2→3→ null ↑ ↓ └───┘

在递归到1节点，2.next=1,1.next=null

1→2←3↑ ↓ └───┘

publicListNodereverseList(ListNodehead){if(head==null||head.next==null){returnhead;}ListNodenewHead=reverseList(head.next);head.next.next=head;head.next=null;returnnewHead;}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

3.回文链表

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：
链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路：数组存储

将链表中的数值存储到数组中，然后在数组中设置左右指针进行比较。
空间复杂度：O(n)

publicbooleanisPalindrome(ListNodehead){int[]arr=newint[100000];inti=0;while(head!=null){arr[i]=head.val;i++;head=head.next;}//判断是否为回文for(intj=0;j<i/2;j++){if(arr[j]!=arr[i-1-j]){returnfalse;}}returntrue;}

解题思路：快慢指针+反转链表⭐

1. 找链表中点
2. 反转后半部分
3. 前半部分和后半部分比较

• 找链表中点：使用快慢指针，fast 走两步，slow 走一步，所以 fast 到末尾时，slow 正好到中间。

• 反转后半部分的内容（slow.next作为第一个需要进行处理的反转点）
• 比较两个链表

publicbooleanisPalindrome(ListNodehead){//找到链表的中间点ListNodeslow=head,fast=head;while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}//将链表的后半部分反转ListNodeprev=null;ListNodecur=slow.next;while(cur!=null){ListNodenext=cur.next;cur.next=prev;prev=cur;cur=next;}//判断是否为回文while(prev!=null){if(head.val!=prev.val){returnfalse;}head=head.next;prev=prev.next;}returntrue;}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

4.环形链表

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：
链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

解题思路：快慢指针

slow 每次走 1 步，fast 每次走 2 步。一旦都进入环里，fast 每一轮相对于 slow 都会多走一步。所以就相当于：slow 不动，fast 每轮靠近 slow 1 个节点。环长度有限，所以最终一定追上。

publicbooleanhasCycle(ListNodehead){//快慢指针ListNodeslow=head;ListNodefast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){returntrue;}}returnfalse;}

扩展：环形链表 II

环形链表 II

在题目的基础上增加对入环节点的输出

a = head 到入口的距离
b = 入口到第一次相遇点的距离
c = 相遇点继续走回入口的距离
L = b + c 为环的长度

快慢指针相遇时，慢针走过的节点长度为：slow = a + b + xL。
快慢指针走的距离相差两倍，即 fast = 2slow
同时快指针比慢指针多走了 n 圈 ，即 fast - slow = nL

=>可以得到 slow = nL = a + b + xL
=>可以得到 a + b = kL
=> a + b 即为头节点 head 到相遇点的距离，kL 即为从相遇点开始走过的圈

publicListNodedetectCycle(ListNodehead){ListNodeslow=head;ListNodefast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){//找到环的入口slow=head;while(slow!=fast){slow=slow.next;fast=fast.next;}returnslow;}}returnnull;}

扩展，输出入环节点，环的最后一个节点，环中包含几个节点

5.合并两个有序链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

解题思路：双指针比较

publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodedummy=newListNode(0);ListNodecur=dummy;while(list1!=null&&list2!=null){if(list1.val<list2.val){cur.next=list1;list1=list1.next;}else{cur.next=list2;list2=list2.next;}cur=cur.next;}cur.next=list1!=null?list1:list2;returndummy.next;}