【Java版oj】链表的回文结构

短命女 2024-04-01 09:03 176阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

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

> ## 一、原题再现 ##
> 
> [链表的回文结构\_牛客题霸\_牛客网][Link 1]
> 
> 较难 通过率：30.08% 时间限制：3秒 空间限制：32M
> 
> ### 描述 ###
> 
> 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
> 
> 给定一个链表的头指针**A**，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
> 
> 测试样例：
> 
> 1->2->2->1  
> 返回：true

> ## 二、问题分析 ##
> 
> 首先我们要了解回文结构是什么，最典型的一个例子是：上海自来水来自海上。
> 
> 故而解决这个题目有三步：1、尝试找到链表的中间结点。2、反转其中的一半链表；得到两条链表。3、依次比较两个链表中的每个结点，如果全部相等则返回true，存在不一样就返回false。
> 
> 牛客题中有一个注意点，就是它链表的构造方法没有给定无参构造，所以我们在开辟新链表结点时要用有参构造 。即得赋值ListNode fakeHeadHead=new ListNode(-1);而不能ListNode fakeHead=new ListNode();
> 
> 关于链表逆置的详细讲法指路☞ [http://t.csdn.cn/SHuUq][http_t.csdn.cn_SHuUq]

> ## 三、完整代码 ##
> 
>     import java.util.*;
>     
>     /*
>     public class ListNode {
>         int val;
>         ListNode next = null;
>     
>         ListNode(int val) {
>             this.val = val;
>         }
>     }*/
>     public class PalindromeList {
>     //遍历求结点个数
>     private int sizeOf(ListNode head){
>             int count=0;
>             for (ListNode cur=head; cur!=null ;cur=cur.next ) {
>                 count++;
>             }
>             return  count;
>         }
>     //求中间结点位置
>         private ListNode middleNode(ListNode head){
>             int size=sizeOf(head);
>             for(int i=0;i<size/2;i++){
>                 head= head.next;
>             }
>             return head;
>         }
>     //逆置后面一半的链表得到新的链表
>         private ListNode reverse(ListNode head){
>             ListNode fakeHead=new ListNode(-1);
>             fakeHead.next=head;
>             ListNode pre=null;
>             ListNode cur=head;
>             while(cur!=null){
>                 ListNode curLast=cur.next;
>                 cur.next=pre;
>                 pre=cur;
>                 cur=curLast;
>             }
>             return pre;
>         }
>         public boolean chkPalindrome(ListNode A) {
>             // write code here
>             ListNode B1=A;
>             // 找到链表的中间结点
>             ListNode midNode=middleNode(A);
>             // 以中间结点为头结点进行逆置
>             ListNode B2=reverse(midNode);
>             // 全部相等：回文  true
>             // 存在不相等：不是回文 false
>             while(B1!=null&&B2!=null){
>                 if(B1.val!=B2.val){
>                     // 存在不相等
>                     return false;
>                 }
>                 B1=B1.next;
>                 B2=B2.next;
>             }
>             // 全部相等
>             return true;
>         }
>     }
> 
> ![c4859edbc2b94513a48d86dd4b73d562.png][]

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

![06f4cdf2689043e397a51b49fc285d5f.png][]

[Link 1]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[http_t.csdn.cn_SHuUq]: http://t.csdn.cn/SHuUq
[c4859edbc2b94513a48d86dd4b73d562.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4390696f980a4880bb726842d421a96c.png
[06f4cdf2689043e397a51b49fc285d5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8c64769fd9d44340b1a2e11c16d80bdc.png