题解 | #判断一个链表是否为回文结构,时间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-21 13:41
点赞 评论 收藏
分享
白火同学:先说结论,准大三不是特别好找实习,boss沟通300+没有实习是很正常的情况。一是暑期实习时间太短了,二是在这么多准大四都找不到实习,从实习时间和掌握技术层面,企业会优先看他们。 再说简历,其实985本+准大三到这水平的简历也很优秀了,要说的话,项目经历可以再优化一下,可以基本围绕采取STAR原则,分为项目概述、技术架构、技术亮点、实现结果,再发给AI润色一下。 最后说操作,准大三的话,如果想找实习那就多投,不过现在也7月中旬了,时间上已经略晚了。如果7月底实在找不到,也可以多刷点算法,多学点技术,这实习也不至于一定得有,当然有更好。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-23 14:10
码农索隆:成年人最直白的答复:已读不回
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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