题解 | #判断一个链表是否为回文结构,时间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 ;
    }
}

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

分享一个菜鸟的成长记录

全部评论

相关推荐

面向对象的火龙果很爱...:去吃一顿炸鸡就走
点赞 评论 收藏
分享
06-17 21:57
门头沟学院 Java
白友:噗嗤,我发现有些人事就爱发这些,明明已读不回就行了,就是要恶心人
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 18:06
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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