题解 | #链表的回文结构#

链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

空间复杂度O(n)
时间复杂度O(n)
fast走两步slow走一步,fast走完的时候slow到中间点
把中间点之后的链表翻转
fast回到头,和slow一起走(每次走一步)
如果回文,从头走的和从中间走的每个val值都相同

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        ListNode fast = A;
        ListNode slow = A;
        ListNode prev = null;
        //找到中间位置
        while(null != fast && null != fast.next) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow;
        //反转后半截链表
        slow = reverseList(fast);
        //把反转后的链表和前面的连接起来
        prev.next = slow;
        //fast回到初始位置
        fast = A;
        while(null!=slow) {
            if(slow.val!=fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
    public ListNode reverseList(ListNode head) {
        if(null == head || null == head.next) {
            return head;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while(null!=cur) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        head.next = null;
        return prev;
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-21 13:41
点赞 评论 收藏
分享
弦五Strings:他之所以会举报你代课是因为在这种人眼里正常上课就是正义代课就是邪恶,典型二极管思维,处理方法就是私下沟通,你就说你自己家里经济困难或者家里父母生病什么之类的,需要去打工挣钱,用尽孝的正义对冲他认为的上课的正义,他可能就妥协了。
我的实习日记
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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