160. 相交鏈表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {/*** 查找兩個鏈表的相交節點* @param headA 第一個鏈表的頭節點* @param headB 第二個鏈表的頭節點* @return 相交的節點，如果不相交則返回null*/public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 使用HashSet來存儲已經訪問過的節點Set<ListNode> visited = new HashSet<ListNode>();// 遍歷第一個鏈表headA，將所有節點存入HashSetListNode temp = headA;while (temp != null) {visited.add(temp); // 將當前節點加入已訪問集合temp = temp.next; // 移動到下一個節點}// 遍歷第二個鏈表headB，檢查每個節點是否在HashSet中存在temp = headB;while (temp != null) {// 如果當前節點已存在于HashSet中，說明是相交節點if (visited.contains(temp)) {return temp; // 返回相交節點}temp = temp.next; // 移動到下一個節點}// 如果遍歷完headB都沒有找到相交節點，返回nullreturn null;}
}代碼解讀：尋找兩個鏈表的交點
這段代碼實現了在Java中尋找兩個單鏈表相交節點的功能。以下是詳細解讀：
方法簽名
public ListNode getIntersectionNode(ListNode headA, ListNode headB)
參數：兩個鏈表的頭節點?
headA?和?headB返回值：兩個鏈表相交的節點，如果不相交則返回?
null實現思路
代碼使用了哈希集合的方法來解決問題，具體步驟如下：
遍歷第一個鏈表：將鏈表A的所有節點存入一個HashSet中
遍歷第二個鏈表：檢查鏈表B的每個節點是否存在于HashSet中
找到交點：如果存在，則該節點就是交點；如果遍歷完都沒有找到，則返回null
代碼逐行解析
Set<ListNode> visited = new HashSet<ListNode>();
創建一個HashSet用于存儲鏈表節點
ListNode temp = headA; while (temp != null) {visited.add(temp);temp = temp.next; }
遍歷鏈表A，將所有節點添加到HashSet中
temp = headB; while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next; }
遍歷鏈表B，檢查每個節點是否存在于HashSet中
如果存在，則立即返回該節點（第一個相交節點）
return null;
如果遍歷完鏈表B都沒有找到相交節點，返回null
復雜度分析
時間復雜度：O(m+n)，其中m和n分別是兩個鏈表的長度
空間復雜度：O(m)，需要存儲鏈表A的所有節點
其他解法
這種方法雖然直觀，但需要額外空間。還有兩種更優的空間O(1)解法：
雙指針法：
計算兩個鏈表的長度
讓長鏈表的指針先移動長度差步
然后兩個指針同步前進，相遇點即為交點
環形檢測法：
將鏈表A的尾節點連接到鏈表B的頭節點
使用快慢指針檢測環的起點，即為交點
最后需要恢復鏈表結構
邊界情況
兩個鏈表都為空
一個鏈表為空
兩個鏈表不相交
兩個鏈表完全重合
交點在鏈表頭部或尾部
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 {/*** 反轉單鏈表* @param head 原鏈表的頭節點* @return 反轉后新鏈表的頭節點*/public ListNode reverseList(ListNode head) {// prev指針用于記錄前一個節點，初始為null（因為反轉后原頭節點將指向null）ListNode prev = null;// curr指針用于遍歷鏈表，初始指向原鏈表頭節點ListNode curr = head;// 遍歷鏈表直到當前節點為null（到達鏈表尾部）while (curr != null) {// 1. 先保存當前節點的下一個節點（否則修改指針后會丟失）ListNode next = curr.next;// 2. 反轉指針方向：當前節點的next指向前一個節點curr.next = prev;// 3. 移動prev指針到當前節點（為下一次迭代做準備）prev = curr;// 4. 移動curr指針到之前保存的下一個節點curr = next;}// 循環結束時，prev指向原鏈表的最后一個節點，即新鏈表的頭節點return prev;}
}算法圖解
假設原始鏈表為：1 → 2 → 3 → 4 → null
執行過程：
初始狀態：prev = null, curr = 1
第一次迭代后：null ← 1 2 → 3 → 4 → null
第二次迭代后：null ← 1 ← 2 3 → 4 → null
第三次迭代后：null ← 1 ← 2 ← 3 4 → null
第四次迭代后：null ← 1 ← 2 ← 3 ← 4
最終返回節點4作為新鏈表的頭節點
關鍵點說明
三指針技術：
prev：記錄前一個節點
curr：當前處理節點
next：臨時保存下一個節點指針操作順序：
必須先保存
next = curr.next，否則反轉后會丟失后續鏈表然后才能修改
curr.next指向最后移動
prev和curr指針終止條件：
當
curr == null時循環結束此時
prev指向原鏈表的最后一個節點（新鏈表的頭節點）邊界情況處理：
空鏈表（head == null）：直接返回null
單節點鏈表：自動正確處理
復雜度分析
時間復雜度：O(n)，只需遍歷鏈表一次
空間復雜度：O(1)，只使用了固定數量的指針變量
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) {ListNode temp=head;List<Integer> vals = new ArrayList<Integer>();while(temp!=null){vals.add(temp.val);temp=temp.next;}int left=0;int length=vals.size();int right=length-1;while(left<right){if(vals.get(left)!=vals.get(right)){return false;}left++;right--;}return true;}
}算法分析
方法思路
存儲階段：將鏈表所有節點的值按順序存入一個ArrayList
驗證階段：使用雙指針法，從列表兩端向中間比較元素是否對稱
時間復雜度
O(n)：需要完整遍歷鏈表兩次（一次存儲，一次比較）
其中n是鏈表的長度
空間復雜度
O(n)：需要使用額外空間存儲所有節點的值
141. 環形鏈表
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {/*** 檢測鏈表是否有環* @param head 鏈表頭節點* @return 如果鏈表有環返回true，否則返回false*/public boolean hasCycle(ListNode head) {// 處理邊界情況：空鏈表或單節點無環if (head == null || head.next == null) {return false;}// 初始化快慢指針ListNode slow = head; // 慢指針每次走1步ListNode fast = head.next; // 快指針每次走2步// 當快慢指針不相遇時繼續循環while (slow != fast) {// 如果快指針到達鏈表末尾，說明無環if (fast == null || fast.next == null) {return false;}// 移動指針slow = slow.next; // 慢指針走1步fast = fast.next.next; // 快指針走2步}// 快慢指針相遇，說明有環return true;}
}算法原理（Floyd判圈算法）
核心思想
使用兩個指針，一個慢指針（每次移動1步），一個快指針（每次移動2步）
如果鏈表無環，快指針會先到達末尾（null）
如果鏈表有環，快指針最終會追上慢指針（相遇）
為什么這樣能工作
無環情況：快指針會先到達鏈表末尾（null）
有環情況：
快指針每次比慢指針多走1步
經過若干步后，快指針會繞環一圈追上慢指針
可以證明最多需要O(n)時間就能檢測出環
關鍵點解析
指針初始化：
慢指針
slow從head開始快指針
fast從head.next開始（避免第一次循環就滿足slow==fast）循環條件：
當
slow != fast時繼續循環如果相等則跳出循環，返回true（有環）
終止條件檢查：
檢查
fast == null || fast.next == null因為fast走得快，只需要檢查fast是否到末尾
指針移動：
慢指針每次移動1步：
slow = slow.next快指針每次移動2步：
fast = fast.next.next復雜度分析
時間復雜度：O(n)
無環情況：快指針到達末尾，最多n/2步
有環情況：慢指針最多走一圈就會被快指針追上
空間復雜度：O(1)
只使用了兩個額外指針，常數空間
邊界情況處理
空鏈表：直接返回false
單節點鏈表：直接返回false（除非自環，但題目通常不考慮）
大環/小環：算法都能正確處理
環在頭部/尾部：都能正確檢測
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){return null;}ListNode slow = head; // 慢指針ListNode fast = head; // 快指針while(fast!=null){slow=slow.next;if(fast.next!=null){fast=fast.next.next;}else{return null;}if(slow==fast){ListNode temp=head;while(temp!=slow){temp=temp.next;slow=slow.next;}return temp;}}return null;}
}算法原理（Floyd判圈算法的擴展）
第一階段：檢測環的存在
快指針每次移動2步，慢指針每次移動1步
如果快指針遇到null，說明鏈表無環
如果快慢指針相遇，說明鏈表有環
第二階段：確定環的起點
當快慢指針相遇后，將一個指針(temp)重新指向鏈表頭部
temp和slow指針每次都移動1步
當它們再次相遇時，相遇點就是環的起點
數學證明
設：
鏈表頭到環起點的距離為a
環起點到相遇點的距離為b
相遇點回到環起點的距離為c
環的長度為L = b + c
當快慢指針相遇時：
慢指針走的距離：a + b
快指針走的距離：a + b + k*L (k為快指針繞環的圈數)
因為快指針速度是慢指針的2倍：
2(a + b) = a + b + kL
=> a + b = kL
=> a = k*L - b = (k-1)*L + c這意味著：從鏈表頭走a步，等于從相遇點走c步加上整數倍的環長。因此，兩個指針分別從頭節點和相遇點出發，以相同速度前進，必將在環起點相遇。
復雜度分析
時間復雜度：O(n)
第一階段最多需要O(n)時間檢測環
第二階段最多需要O(n)時間找到環起點
空間復雜度：O(1)
只使用了固定數量的指針變量
邊界情況處理
空鏈表：直接返回null
單節點無環：快指針會走到null
單節點自環：能正確檢測并返回該節點
環在頭部：能正確返回頭節點
環在尾部：能正確返回環起點
