小试牛刀——链表第三篇

约定不等于承诺〃 2023-09-27 11:53 126阅读 0赞

![在这里插入图片描述][b58e14a606c14e76832adc977e9ba0ba.gif_pic_center]

>  个人主页：[熬夜磕代码丶][Link 1]  
>  作品专栏: [数据结构与算法][Link 2]  
>  我变秃了，也变强了  
> 最近接触到一个很好用的软件:Apifox Apifox = Postman + Swagger + Mock + JMeter  
> 点我进入[Apifox][]

#### 文章目录 ####

*  一、链表的回文结构
 *  二、环形链表
 *  三、环形链表II

## 一、链表的回文结构 ##

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。  
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。  
![在这里插入图片描述][03df7d2fdaa44a718a42d02c9bfe538d.png]

public class PalindromeList {
        
        public boolean chkPalindrome(ListNode A) {
        
            if (A == null) {
        
                return false;
            }
            if (A.next == null) {
        
                return true;
            }
            ListNode fast = A;
            ListNode slow = A;
            while (fast != null && fast.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode cur = slow.next;
                slow.next = null;
            while (cur != null) {
        
                ListNode curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            while (slow != A) {
        
                if(slow.val != A.val) {
        
                    return false;
                }
                if(A.next == slow) {
        
                    return true;
                }
                slow = slow.next;
                A = A.next;
            }
            return true;
        }
    }

## 二、环形链表 ##

给你一个链表的头节点 head ，判断链表中是否有环。  
![在这里插入图片描述][816b368b509b46518af1db6eeed6605d.png]

public boolean hasCycle(ListNode head) {
        
            if(head == null || head.next == null) {
        
                return false;
            }
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow) {
        
                    return true;
                }
    
            }
            return false;
        }

## 三、环形链表II ##

定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。  
![在这里插入图片描述][83422b0fe7cb4ec6bf2f20ee2ae34abc.png]

public ListNode detectCycle(ListNode head) {
        
            if(head == null || head.next == null) {
        
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow) {
        
                    while(slow != head) {
        
                        slow = slow.next;
                        head = head.next;
                    }
                    return head;
                }
            }
            return null;
        }

[b58e14a606c14e76832adc977e9ba0ba.gif_pic_center]: https://img-blog.csdnimg.cn/b58e14a606c14e76832adc977e9ba0ba.gif#pic_center
[Link 1]: https://blog.csdn.net/buhuisuanfa?spm=1018.2226.3001.5343
[Link 2]: https://blog.csdn.net/buhuisuanfa/category_11999355.html?spm=1001.2014.3001.5482
[Apifox]: http://apifox.cn/a103aoye
[03df7d2fdaa44a718a42d02c9bfe538d.png]: https://img-blog.csdnimg.cn/03df7d2fdaa44a718a42d02c9bfe538d.png
[816b368b509b46518af1db6eeed6605d.png]: https://img-blog.csdnimg.cn/816b368b509b46518af1db6eeed6605d.png
[83422b0fe7cb4ec6bf2f20ee2ae34abc.png]: https://img-blog.csdnimg.cn/83422b0fe7cb4ec6bf2f20ee2ae34abc.png