文章目录1.相交链表题目解题思路双指针2.反转链表题目解题思路指向反转迭代法⭐解题思路从前向后递归翻转递归法3.回文链表题目解题思路数组存储解题思路快慢指针反转链表⭐4.环形链表题目解题思路快慢指针扩展环形链表 II5.合并两个有序链表题目解题思路双指针比较1.相交链表题目给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。图示两个链表在节点 c1 开始相交题目数据 保证 整个链式结构中不存在环。注意函数返回结果后链表必须 保持其原始结构 。自定义评测评测系统 的输入如下你设计的程序 不适用 此输入intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表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 中节点数目为 mlistB 中节点数目为 n1 m, n 3 * 10^41 Node.val 10^50 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB]进阶你能否设计一个时间复杂度 O(m n) 、仅用 O(1) 内存的解决方案解题思路双指针A 链表独有部分长度 aB 链表独有部分长度 b公共部分长度 c设置两个指针 pA 和 pB让 pA 走完 A 后再走 B当第二遍走到相交节点的时候走过的长度为 acb让 pB 走完 B 后再走 A当第二遍走到相交节点的时候走过的长度为 bca也就是说两个指针在第二遍走到相交节点时的路径长度一样此时如果两指针相等就判定为相交节点如果都指向空c0两指针都指向末尾此时就没有相交节点要么两个指针每次逐步向后移动一位直到判定为相等此时相交节点第一次遍历如果其中有指针指向null就变换为另一条的头节点第二次便利两个同时指向null判定为不相交经过两次遍历后要么都指向null要么相交指向同一个相交节点如果两个链表长度相同即ab那第一次遍历的时候就能找到了publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){ListNodepAheadA;ListNodepBheadB;while(pA!pB){pApAnull?headB:pA.next;pBpBnull?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的下一个指向设置为nullnull ←12→3→4→5→ null ↑ ↑ ↑ pre cur nextnull ←12→3→4→5→ null ↑ ↑ ↑ pre cur next处理完成后原来cur的位置变为pre原来next即变成下一个要处理的节点cur。直到处理到末尾即next null此时返回当前节点为头节点publicListNodereverseList(ListNodehead){ListNodeprevnull;ListNodecurrhead;//考虑为[]的情况此时没有next,cur为nullwhile(curr!null){ListNodenextcurr.next;curr.nextprev;prevcurr;currnext;}returnprev;}时间复杂度O(n)空间复杂度O(1)不能直接拷贝value值进行反转这样只是修改了节点存储的数据并没有改变节点之间的 next 指向。反转链表本质上是反转节点之间的连接关系。解题思路从前向后递归翻转递归法从后向前处理节点当第一次调用reverseList(1)后续会递归到reverseList(2)、reverseList(3)node1 ↓[1]→[2]→[3]到3之后返回为null此时开始处理reverseList(2)此时叫 3.next22.nextnull2→3→ null ↑ ↓ └───┘在递归到1节点2.next1,1.nextnull1→2←3↑ ↓ └───┘publicListNodereverseList(ListNodehead){if(headnull||head.nextnull){returnhead;}ListNodenewHeadreverseList(head.next);head.next.nexthead;head.nextnull;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[]arrnewint[100000];inti0;while(head!null){arr[i]head.val;i;headhead.next;}//判断是否为回文for(intj0;ji/2;j){if(arr[j]!arr[i-1-j]){returnfalse;}}returntrue;}解题思路快慢指针反转链表⭐找链表中点反转后半部分前半部分和后半部分比较找链表中点使用快慢指针fast 走两步slow 走一步所以 fast 到末尾时slow 正好到中间。反转后半部分的内容slow.next作为第一个需要进行处理的反转点比较两个链表publicbooleanisPalindrome(ListNodehead){//找到链表的中间点ListNodeslowhead,fasthead;while(fast.next!nullfast.next.next!null){slowslow.next;fastfast.next.next;}//将链表的后半部分反转ListNodeprevnull;ListNodecurslow.next;while(cur!null){ListNodenextcur.next;cur.nextprev;prevcur;curnext;}//判断是否为回文while(prev!null){if(head.val!prev.val){returnfalse;}headhead.next;prevprev.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^5pos 为 -1 或者链表中的一个 有效索引 。进阶你能用 O(1)即常量内存解决此问题吗解题思路快慢指针slow 每次走 1 步fast 每次走 2 步。一旦都进入环里fast 每一轮相对于 slow 都会多走一步。所以就相当于slow 不动fast 每轮靠近 slow 1 个节点。环长度有限所以最终一定追上。publicbooleanhasCycle(ListNodehead){//快慢指针ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){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){ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){//找到环的入口slowhead;while(slow!fast){slowslow.next;fastfast.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 100l1 和 l2 均按 非递减顺序 排列解题思路双指针比较publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodedummynewListNode(0);ListNodecurdummy;while(list1!nulllist2!null){if(list1.vallist2.val){cur.nextlist1;list1list1.next;}else{cur.nextlist2;list2list2.next;}curcur.next;}cur.nextlist1!null?list1:list2;returndummy.next;}