LeetCode 热题 100 之 160. 相交链表 206. 反转链表 234. 回文链表 141. 环形链表 142. 环形链表 II

160. 相交链表206. 反转链表234. 回文链表141. 环形链表142. 环形链表 II160. 相交链表public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA null || headB null) return null; ListNode pA headA, pB headB; while (pA ! pB) { pA pA null ? headB : pA.next; pB pB null ? headA : pB.next; } return pA; } }解题思路1双指针双指针法是最优解时间复杂度 O(nm)空间复杂度 O(1)初始化两个指针pA和pB分别指向链表headA和headB的头节点。同时遍历两个链表pA走到headA末尾时重新指向headBpB走到headB末尾时重新指向headA。当pA和pB相遇时该节点即为相交的起始节点若遍历到末尾仍未相遇则两链表不相交返回null。原理两个指针走过的总路程相等lenA lenB若存在相交节点必然会在相交点相遇代码解释边界处理若任一链表为空直接返回null。指针遍历pA和pB交替遍历两个链表保证最终路程相等。相遇判断当pA pB时要么是相交节点要么同时到达末尾null直接返回即可。public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA 0, lenB 0; ListNode pA headA, pB headB; // 计算长度 while (pA ! null) { lenA; pA pA.next; } while (pB ! null) { lenB; pB pB.next; } // 长链表先走 pA headA; pB headB; if (lenA lenB) { for (int i 0; i lenA - lenB; i) pA pA.next; } else { for (int i 0; i lenB - lenA; i) pB pB.next; } // 同时遍历找相遇点 while (pA ! pB) { pA pA.next; pB pB.next; } return pA; } }解题思路2长度差法先计算两个链表的长度让长链表的指针先走长度差的步数再同时遍历相遇点即为相交节点206. 反转链表/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 保存下一个节点 curr.next prev; // 翻转当前节点指向 prev curr; // prev 前进 curr next; // curr 前进 } return prev; } }解题思路1迭代法核心思路用三个指针逐个翻转节点的指向从前往后遍历链表将当前节点的next指向前一个节点。初始化prev null前一个节点、curr head当前节点、next null临时保存下一个节点遍历链表保存curr.next到next避免断链将curr.next指向prev完成当前节点的翻转prev移动到currcurr移动到next遍历结束后prev就是新链表的头节点class Solution { public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseList(head.next); head.next.next head; head.next null; return newHead; } }解题思路2递归法核心思路递归到链表末尾从后往前逐层翻转节点指向。递归终止条件head null或head.next null直接返回head递归调用reverseList(head.next)得到子链表的新头节点将head.next.next head让子链表的末尾节点指向当前节点将head.next null断开原指向避免成环234. 回文链表/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if (head null || head.next null) return true;a // 1. 快慢指针找中点 ListNode slow head, fast head; while (fast.next ! null fast.next.next ! null) { slow slow.next; fast fast.next.next; } // 2. 反转后半链表 ListNode prev null, curr slow.next; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } // 3. 双指针比较 ListNode left head, right prev; while (right ! null) { if (left.val ! right.val) return false; left left.next; right right.next; } return true; } }解题思路1双指针 反转后半链表用快慢指针找到链表中点快指针走 2 步慢指针走 1 步快指针到末尾时慢指针指向中点。反转链表的后半部分。用双指针分别从链表头和反转后的后半部分头开始遍历逐一比较节点值是否相等。若所有节点值都相等则为回文链表否则不是。class Solution { public boolean isPalindrome(ListNode head) { ListInteger list new ArrayList(); ListNode curr head; while (curr ! null) { list.add(curr.val); curr curr.next; } int left 0, right list.size() - 1; while (left right) { if (!list.get(left).equals(list.get(right))) return false; left; right--; } return true; } }解题思路2转数组 双指针遍历链表将所有节点值存入数组。用双指针分别从数组首尾向中间遍历逐一比较元素是否相等。141. 环形链表/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head null || head.next null) return false; ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) return true; } return false; } }解题思路1快慢指针法Floyd 判圈算法初始化两个指针slow慢指针每次走 1 步和fast快指针每次走 2 步。若链表无环快指针会先到达链表末尾fast null或fast.next null直接返回false。若链表有环快指针最终会和慢指针在环内相遇此时返回true。原理快指针相对慢指针的速度为 1 步 / 次若存在环两者必然会在环中相遇。public class Solution { public boolean hasCycle(ListNode head) { SetListNode visited new HashSet(); while (head ! null) { if (visited.contains(head)) return true; visited.add(head); head head.next; } return false; } }解题思路2哈希表法超低效率遍历链表用哈希集合记录已访问的节点。若当前节点已在集合中说明存在环若遍历到末尾仍未重复则无环。142. 环形链表 II/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (head null || head.next null) return null; ListNode slow head, fast head; // 1. 快慢指针找相遇点 while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) break; // 找到相遇点 } // 无环情况 if (fast null || fast.next null) return null; // 2. slow 移回头部同速遍历找入口 slow head; while (slow ! fast) { slow slow.next; fast fast.next; } return slow; } }解题思路1快慢指针法Floyd 判圈算法检测环并找到相遇点用慢指针slow每次走 1 步和快指针fast每次走 2 步遍历链表。若fast或fast.next为null说明无环返回null。若slow与fast相遇说明存在环。找到环的入口相遇后将slow移回链表头节点fast留在相遇点。让slow和fast以相同速度每次 1 步继续遍历两者再次相遇的节点即为环的入口。数学原理设链表头到环入口的距离为a环入口到相遇点的距离为b环的长度为c。相遇时slow走过的路程abfast走过的路程abk⋅ck 为绕环的圈数k≥1因为fast速度是slow的 2 倍所以2(ab)abk⋅c化简得 ak⋅c−b。这意味着从链表头到环入口的距离 从相遇点绕环k圈后再走到环入口的距离。因此让slow从头部出发fast从相遇点出发同速前进必然在环入口相遇。public ListNode detectCycle(ListNode head) { SetListNode visited new HashSet(); while (head ! null) { if (visited.contains(head)) return head; visited.add(head); head head.next; } return null; }解题思路2哈希表法超低效率遍历链表用哈希集合记录已访问的节点第一个重复出现的节点即为环的入口。核心题型与最优解法汇总题目核心解法时间复杂度空间复杂度核心思想160. 相交链表双指针法路程对等O(nm)O(1)两指针分别遍历 AB 和 BA路程相等则必在相交点相遇206. 反转链表迭代法双指针O(n)O(1)逐个翻转节点指向用 prev/curr/next 三个指针完成方向反转234. 回文链表快慢指针 反转后半链表O(n)O(1)找中点→反转后半段→双指针对比前后段实现原地判断141. 环形链表快慢指针Floyd 判圈O(n)O(1)快指针速度 2 倍于慢指针有环则必相遇142. 环形链表 II快慢指针 入口定位O(n)O(1)相遇后慢指针回起点双指针同速遍历相遇点即为环入口