题解 | #判断一个链表是否为回文结构,时间O(n),空间O(1)#

判断一个链表是否为回文结构

http://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    //时间O(n) 空间O(1)
    public boolean isPail (ListNode head) {
        if(head == null) return false ;
        //只有一个节点
        if(head.next == null) return true ;
        //只有两个节点
        if(head.next.next == null) {
            if(head.val == head.next.val) {
                return true ;
            } else {
                return false ;
            }
        }
        //三个及以上的节点(使用快慢指针,找到中点,将中点以后的链表翻转,
        //然后依次迭代两条链表,判断回文
        ListNode fast = head ;
        ListNode slow = head ;
        while(!(fast.next == null || fast.next.next == null)) {
            fast = fast.next.next ;
            slow = slow.next ;
        }
        //此时slow指向中点,将中点以后的链表翻转
        ListNode left = head ;//左部分
        ListNode tmp = slow.next ;
        slow.next = null ;
        ListNode right = reverse(tmp) ;//右部分
        //开始判断回文
        while(left != null && right != null) {
            if(left.val != right.val) {
                return false ;
            }
            left = left.next ;
            right = right.next ;
        }
        return true ;       
    }
    public ListNode reverse(ListNode list) {
        ListNode pre = null ;
        ListNode cur = list ;
        ListNode nxt = null ;
        while(cur != null) {
            nxt = cur.next ;
            cur.next = pre ;
            pre = cur ;
            cur = nxt ;
        }
        return pre ;
    }
}

一个菜鸟的算法刷题记录 文章被收录于专栏

分享一个菜鸟的成长记录

全部评论

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司7个岗位
点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
06-17 00:26
门头沟学院 Java
程序员小白条:建议换下项目,智能 AI 旅游推荐平台:https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台:https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆:https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的,然后最好能自己拓展的,分布式这种尽量别去写,不然你只能背八股文了,另外实习的话要多投,尤其是学历不利的情况下,多找几段实习,最好公司title大一点的
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务