《新星计划之链表》环形链表、回文链表（图解分析）

分手后的思念是犯贱 2024-04-23 15:37 35阅读 0赞

> ✅作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
> 
> ?博客首页：[是小鱼儿哈][Link 1]
> 
> ?系列专栏：[JavaSE学习笔记][JavaSE]
> 
> ?每日一句：**尽自己最大的努力，抱最大的希望，作最坏的打算。**
> 
> ?博主也在学习阶段，如发现问题请告知，非常感谢?

**目录**

环形链表

回文链表

--------------------

## 环形链表 ##

![f6b0f1f1e931493980518e1754734667.png][]

>  **原题链接**：[环形链表][Link 2]

> 分析：**对于链表的很多题目我们经常会用到一种思想——双指针，我们这道题目也用到了双指针这一思想，即定义两个对结点的引用变量fast和slow，他们一开始都分别指向头结点。但不同的是fast每次移动两个结点，slow每次移动一个结点。**

这样的话如果链表中存在环的话，他们两个一定会相遇，如图所示：

![df8f2aeba032770d580827ae7529c7b8.gif][]

代码如下：

// 环形链表
    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这个判断条件不能丢**

为啥呢？如图所示：

![c121de0bdf82474dab0c2d8b7a808d45.png][]

--------------------

## 回文链表 ##

![69e25fdde6564b7d97a479c42009adb3.png][]

> **原题链接**：[回文链表][Link 3]

> **思路：一开始我想是反转链表后再与原链表比较，但问题是再我们反转链表的过程中原来的链表已经变了。**

![1057d3e2027a4fed909eb728c5556e6c.png][]

?所以我们不妨换个思路，**你看如果一个链表是回文链表的话：它是不是正好分成了两个部分，既然我们不能反转整个链表，那么我们能不能对链表的后半部分进行反转，这样如果反转后的后半部分和前半部分是重合的，那么就说明这是一个回文链表。**

?那么问题又来了？我们怎样把链表分为两部分呢？就是如上图所示只有我们能够找到链表的中间位置3就好。

**我们定义两个结点的引用fast和slow，fast每次移动两个结点，slow每次移动一个结点。**

能够移动的条件就是：

>     while (fast != null && fast.next != null)

开始时

![51ea6ce18ef043c1ad868ef619754ff4.png][]

结束时

![3631f9fa66824e5dbdae9c38c518cc2c.png][]

> **可以发现当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;
        }
    
    }

[Link 1]: https://blog.csdn.net/weixin_61061381?type=blog
[JavaSE]: https://blog.csdn.net/weixin_61061381/category_11724948.html?spm=1001.2014.3001.5482
[f6b0f1f1e931493980518e1754734667.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d714a1d4fb6f41e48363fb54b1a9b2c1.png
[Link 2]: https://leetcode-cn.com/problems/linked-list-cycle/
[df8f2aeba032770d580827ae7529c7b8.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/0c171ed1b8d247d59d11541707023dc6.gif
[c121de0bdf82474dab0c2d8b7a808d45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5cdff21d824348e7bcb314a1120af92f.png
[69e25fdde6564b7d97a479c42009adb3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d97c861b43db418bb0ca899957080728.png
[Link 3]: https://leetcode-cn.com/problems/aMhZSa/
[1057d3e2027a4fed909eb728c5556e6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/7fd9e78a14824523b984c0a2d23f5144.png
[51ea6ce18ef043c1ad868ef619754ff4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8614af848de248a19661796b85f7e599.png
[3631f9fa66824e5dbdae9c38c518cc2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/4ce13cb958034ac78163c5e166dffaa2.png