牛客网刷题——链表

阳光穿透心脏的1/2处 2023-10-10 15:01 11阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：流川枫的博客
> 
> 专栏：和我一起学java
> 
> 语录：Stay hungry stay foolish
> 
> 给大家推荐一款好用的神器  
> [Apifox = Postman + Swagger + Mock + JMeter。集接口文档工具、接口Mock工具、接口自动化测试工具、接口调试工具于一体,提升 10 倍研发效率戳我来体验~][Apifox _ Postman _ Swagger _ Mock _ JMeter_Mock_ 10]

**文章目录**

在线Oj链接

1. 题目描述

2. 解题思路

3. 题解

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

## 在线Oj链接 ##

[OR36 链表的回文结构][OR36]

## 1. 题目描述 ##

> 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
> 
> 给定一个链表的头指针**A**，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
> 
> 测试样例：![08ea13bc7f8f4081ba9d0778252efa3c.png][]

## 2. 解题思路 ##

先用快慢指针找到链表的中间节点

再将中间节点后部分的链表反转

然后从链表两头开始比较元素的大小

![869ba8b08a12451b90e10bb14677d118.png][]

对上面这个链表，我们先定义一个快慢指针，fast和slow，让fast走两步，slow走一步，当fast=null或者fast.next=null时，说明slow为中间节点，如下图;

![47ee5e23d45645ec85248fa198e40ecb.png][]

找到中间节点后，我们进行中间节点后的链表反转

定义一个cur记录待反转链表头节点，curNext记录cur，反转后结果如下：![595c0804c8424b36baf8368b82be587c.png][]

此时只需要从两端开始比较对应位置值的大小就可以了

## 3. 题解 ##

import java.util.*;
    
    
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    public class PalindromeList {
        public boolean chkPalindrome(ListNode head) {
            // write code here
            if(head == null){
                return false;
            }
            if(head.next == null){
                return true;
            }
            //找中间点
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=null&&fast.next!=null){
                fast = fast.next.next;
                slow = slow.next;
            }
            //2.反转
            ListNode cur = slow.next;
            while(cur!=null){
                ListNode curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            //3.比较大小
            while(head!=slow){
                if(head.val!=slow.val){
                    return false;
                }
                //链表长度为偶数情况
                if(head.next == slow){
                    return true;
                }
                head = head.next;
                slow = slow.next;
            }
            return true;
        }
    }

在比较大小的时候要注意是偶数的情况，用head.next == slow来解决

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Apifox _ Postman _ Swagger _ Mock _ JMeter_Mock_ 10]: http://apifox.cn/a103liucf
[OR36]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[08ea13bc7f8f4081ba9d0778252efa3c.png]: https://img-blog.csdnimg.cn/08ea13bc7f8f4081ba9d0778252efa3c.png
[869ba8b08a12451b90e10bb14677d118.png]: https://img-blog.csdnimg.cn/869ba8b08a12451b90e10bb14677d118.png
[47ee5e23d45645ec85248fa198e40ecb.png]: https://img-blog.csdnimg.cn/47ee5e23d45645ec85248fa198e40ecb.png
[595c0804c8424b36baf8368b82be587c.png]: https://img-blog.csdnimg.cn/595c0804c8424b36baf8368b82be587c.png