环形链表
原题链接：环形链表
分析：对于链表的很多题目我们经常会用到一种思想——双指针，我们这道题目也用到了双指针这一思想，即定义两个对结点的引用变量fast和slow，他们一开始都分别指向头结点。但不同的是fast每次移动两个结点，slow每次移动一个结点。
这样的话如果链表中存在环的话，他们两个一定会相遇，如图所示：
代码如下：
// 环形链表 public class Solution { public boolean hasCycle(ListNode head) { ListNode fast = head, show = head; while(fast != null && fast.next != null) { fast = fast.next.next; show = show.next; if (fast == show) { return true; // 如果有环的话，他们两个一定能相遇 } } return false; } }
但这里有一个小细节，在while的循环条件里fast != null这个判断条件不能丢
为啥呢？如图所示：
回文链表
原题链接：回文链表
思路：一开始我想是反转链表后再与原链表比较，但问题是再我们反转链表的过程中原来的链表已经变了。
🍑所以我们不妨换个思路，你看如果一个链表是回文链表的话：它是不是正好分成了两个部分，既然我们不能反转整个链表，那么我们能不能对链表的后半部分进行反转，这样如果反转后的后半部分和前半部分是重合的，那么就说明这是一个回文链表。
🍑那么问题又来了？我们怎样把链表分为两部分呢？就是如上图所示只有我们能够找到链表的中间位置3就好。
我们定义两个结点的引用fast和slow，fast每次移动两个结点，slow每次移动一个结点。
能够移动的条件就是：
while (fast != null && fast.next != null)
开始时
结束时
可以发现当fast移动结束后，slow就会移动到中间，那么这样一来移动后的slow所指向的结点就是我们链表的中间结点。
📝总结一下就是：
- 1.用快慢指针找到中间位置，把代码分为前后两个部分
- 2.对后半部分进行旋转操作
- 3.比较前后两个部分是否相等
class Solution { // 首先要找到中间结点 public ListNode midFind(ListNode slow, ListNode fast) { while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; // 此时慢指针所指向的就是中间结点 } // 反转链表，把中间结点之后的结点进行反转 public ListNode reverseList(ListNode cur) { ListNode pre = null; while(cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } // 判断前后两部分是否相等 public boolean isPalindrome(ListNode head) { ListNode dummyHead = new ListNode(0, head); // 设置虚拟头结点，当结点只有较少时方便处理 ListNode mid = midFind(dummyHead, dummyHead); // mid链表的中间结点 // 对中间结点往后的后半部分进行反转 ListNode tail = reverseList(mid.next); while(dummyHead != mid && head != null && tail != null) { if (head.val != tail.val) { return false; } head = head.next; tail = tail.next; } return true; } }
