题解 | #判断一个链表是否为回文结构#

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

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

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

1、题意重述

给定一个链表,请判断该链表是否为回文结构。 回文是指该字符串正序逆序完全一致。

换句话说,就是判断链表倒序以后,然后和原来的链表是否相等。

2、思路整理

使用双指针的思想:

Step1:使用两个指针fast和slow,fast每次走两步,slow每次走一步。

alt

Step2:当fast的指向为空时,记录slow的位置。

alt

Step3:将slow以后的部分进行翻转,并且与之前的部分进行比较。如果相等,则是回文结构,否则不是回文结构。

alt

3、代码实现

  public boolean isPail(ListNode head) {
    ListNode fast = head, slow = head;
    //通过快慢指针找到中点
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    if (fast != null) {
        slow = slow.next;
    }
    slow = reverse(slow); //翻转后半部分
    fast = head;
    while (slow != null) {
        //比较节点值是否相等
        if (fast.val != slow.val)
            return false;
        fast = fast.next;
        slow = slow.next;
    }
    return true;
}

//反转链表
public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

4、复杂度分析

时间复杂度:一层循环,因此时间复杂度为O(N)O(N)

空间复杂度:使用常数级内存地址空间,因此空间复杂度为O(1)O(1)

22年春节特别专栏_双指针 文章被收录于专栏

双指针题解,图片随便找的!

全部评论

相关推荐

点赞 评论 收藏
分享
头像
04-17 09:29
已编辑
湖南农业大学 后端
睡姿决定发型丫:本硕末9也是0offer,简历挂了挺多,只有淘天 美团 中兴给了面试机会,淘天二面挂,美团一面kpi面,中兴一面感觉也大概率kpi(虽然国企,但一面0技术纯聊天有点离谱吧)
点赞 评论 收藏
分享
Rena1ssance_:对的,要是面评没太烂,勤更新简历等捞就行了,腾讯可以无限复活
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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