环形链表
判断是否有环
环形链表是指链表中的某些节点的 next 指针指向了链表中的某个前面的节点，导致链表中的节点构成一个环。
思路：快慢指针（Floyd 判圈算法）
我们可以使用 快慢指针 来判断链表中是否有环。这种方法也叫做 Floyd 判圈算法，是一个经典且高效的解法。
• 快指针（slow pointer） 每次移动一步。
• 慢指针（fast pointer） 每次移动两步。
判断条件：
- 如果链表中没有环，快指针最终会遇到 null，这时候说明链表没有环。
- 如果链表有环，快指针和慢指针一定会相遇，因为快指针每次移动两步，而慢指针每次移动一步，快指针追得上慢指针。
// 判断 是否有环
public boolean hasCycle(ListNode head) {
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. 判断环的存在：首先使用快慢指针来判断链表是否有环，如果没有环，则直接返回 null。
2. 找到环的入口：
• 假设链表有环，快慢指针在环内相遇。
• 将其中一个指针从头节点开始，另一个指针保持在相遇位置。
• 然后，两个指针同时每次移动一步。它们相遇的位置就是环的入口。
为什么能这么做？
• 假设链表总共有 n 个节点，其中前 k 个节点在环外，后 n-k 个节点在环内。
• 当快慢指针在环内相遇时，假设慢指针在环内相遇的位置是 X。
• 如果将其中一个指针移回链表的起点，并让两个指针同时移动，每次移动一步，它们必定会在环的入口相遇。
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// 1. 判断有没有环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // 快慢指针相遇，说明有环
break;
}
}
// 如果没有环，直接返回 null
if (fast == null || fast.next == null) {
return null;
}
// 2. 找到环的入口
fast = head; // 快指针移到链表头
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // 返回环的入口
}
双指针
反转链表（Reverse a Linked List）
反转链表是链表操作中最经典的题目之一，特别是在面试中经常出现。这个问题的基本要求是将链表的节点顺序反转。
基本思路：
使用三个指针来反转链表：
1. prev：指向当前节点的前一个节点。
2. cur：指向当前节点。
3. next：指向当前节点的下一个节点。
我们遍历链表，将每个节点的 next 指针指向前一个节点。
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode next = null;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
移除链表中的指定元素（Remove Linked List Elements）
值得注意：移除元素需要保留该节点的前一个节点。
public ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val) {
head = head.next;
}
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
if (curr.val == val) {
prev.next =curr.next;
curr = prev.next;
}else {
prev = curr;
curr = curr.next;
}
}
return head;
}