专栏首页苦逼的码农【链表问题】打卡6:三种方法带你优雅判断回文链表

【链表问题】打卡6:三种方法带你优雅判断回文链表

前言

以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

注:如果你在看代码的时候发现代码排版乱了麻烦告诉我一声,谢谢。

【题目描述】

给定一个链表的头节点 head, 请判断该链表是否为回文结构。

例如:

1->2->1,返回 true.

1->2->2->1, 返回 true。

1->2->3,返回 false。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

普通解法:士:★☆☆☆

进阶解法:尉:★★☆☆

【解答】

方法1

我们可以利用栈来做辅助,把链表的节点全部入栈,在一个一个出栈与链表进行对比,例如对于链表 1->2->3->2->2,入栈后如图:

然后再逐一出栈与链表元素对比。

这种解法比较简单,时间复杂度为 O(n), 空间复杂度为 O(n)。

代码如下

 1//方法1
 2public static boolean f1(Node head) {
 3    if (head == null || head.next == null) {
 4        return true;
 5    }
 6    Node temp = head;
 7    Stack<Node> stack = new Stack<>();
 8    while (temp != null) {
 9        stack.push(temp);
10        temp = temp.next;
11    }
12    while (!stack.isEmpty()) {
13        Node t = stack.pop();
14        if (t.value != head.value) {
15            return false;
16        }
17        head = head.next;
18    }
19    return true;
20}

方法二

真的需要全部入栈吗?其实我们也可以让链表的后半部分入栈就可以了,然后把栈中的元素与链表的前半部分对比,例如 1->2->3->2->2 后半部分入栈后如图:

然后逐个出栈,与链表的前半部分(1->2)对比。这样做的话空间复杂度会减少一半。

代码如下:

 1//方法2
 2public static boolean f(Node head) {
 3    if(head == null || head.next == null)
 4        return true;
 5    Node slow = head;//慢指针
 6    Node fast = head;//快指针
 7    Stack<Node> stack = new Stack<>();
 8    //slow最终指向中间节点
 9    while (fast.next != null && fast.next.next != null) {
10        slow = slow.next;
11        fast = fast.next.next;
12    }
13    System.out.println(slow.value);
14    slow = slow.next;
15    while (slow != null) {
16        stack.push(slow);
17        slow = slow.next;
18    }
19    //进行判断
20    while (!stack.isEmpty()) {
21        Node temp = stack.pop();
22        if (head.value != temp.value) {
23            return false;
24        }
25        head = head.next;
26    }
27    return true;
28}

方法三:空间复杂度为 O(1)。

上道题我们有作过链表的反转的,没看过的可以看一下勒:【链表问题】如何优雅着反转单链表],我们可以把链表的后半部分进行反转,然后再用后半部分与前半部分进行比较就可以了。这种做法额外空间复杂度只需要 O(1), 时间复杂度为 O(n)。

代码如下:

 1//方法3
 2public static boolean f2(Node head) {
 3    if(head == null || head.next == null)
 4        return true;
 5    Node slow = head;//慢指针
 6    Node fast = head;//快指针
 7    //slow最终指向中间节点
 8    while (fast.next != null && fast.next.next != null) {
 9        slow = slow.next;
10        fast = fast.next.next;
11    }
12    Node revHead = reverse(slow.next);//反转后半部分
13    //进行比较
14    while (revHead != null) {
15        System.out.println(revHead.value);
16        if (revHead.value != head.value) {
17            return false;
18        }
19        head = head.next;
20        revHead = revHead.next;
21    }
22    return true;
23}
24//反转链表
25private static Node reverse(Node head) {
26    if (head == null || head.next == null) {
27        return head;
28    }
29    Node newHead = reverse(head.next);
30    head.next.next = head;
31    head.next = null;
32    return newHead;
33}

问题拓展

思考:如果给你的是一个环形链表,并且指定了头节点,那么该如何判断是否为回文链表呢?

【题目描述】

【要求】

【难度】

未知。

【解答】

无。此题为开放题,你可以根据这个设定各种其他要求条件。

- End -

本文分享自微信公众号 - 苦逼的码农(di201805)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【链表问题】打卡10:将搜索二叉树转换成双向链表

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

    帅地
  • 记一次Linux被入侵,服务器变“矿机”全过程

    出处:看雪社区:https://bbs.pediy.com/thread-225163.htm

    帅地
  • 【链表问题】打卡7:将单向链表按某值划分成左边小,中间相等,右边大的形式

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

    帅地
  • 【Leetcode】142.环形链表 II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。有环则返回环的入口...

    Leetcode名企之路
  • leetcode: 92. Reverse Linked List II

    JNingWei
  • 异名解题:反转链表

    在遍历的时候把节点存在数组里面,可以利用reverse方法,也可以利用数组存储特点做顺序记录

    异名
  • 173. 链表插入排序插入排序

    用插入排序对链表排序 样例 Given 1->3->2->0->null, return 0->1->2->3->null

    和蔼的zhxing
  • 有环链表

    一份执着✘
  • LeetCode 19. Remove Nth Node From End of List题目分析代码

    样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数第二个节点之后,这个链表将变成1->2->3->5->null.

    desperate633
  • LintCode 回文链表题目分析代码

    链表由于其特殊的结构,没法像数组那样判断回文,所以比较原始的方法,先找到链表的中间节点,然后将后半部分反转,然后逐个比较即可。 链表中的算法,通常以寻找链表中...

    desperate633

扫码关注云+社区

领取腾讯云代金券