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

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

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

题目描述
给定一个链表,请判断该链表是否为回文结构。

例子: 123321 12321 1 11 此类的即为回文结构

方法一:线性表+双指针
这个方法其实很容易想到,把题目换了,如果不是一条链表判断是否是回文结构,换成是一个数组。
所以我们就可以先遍历一遍链表,然后将里面的值先存放进ArrayList中即可。
那么,我们就很容易想到利用双指针去判断是否是回文结构了!

图片说明
下面直接给出代码~

public boolean isPail (ListNode head) {
        if(head == null)
            return false;
        if(head.next == null)
            return true;
        // 创建一个ArrayList用来存储
        ArrayList<Integer> list = new ArrayList<>();
        // 将链表全部节点的值按顺序放进list
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        // 双指针,一个指向起点,一个指向终点!
        int left = 0, right = list.size()-1;
        while(left < right){
            // 如果不相等,那么则不是回文结构,直接返回false
            // 这里可能有个疑问,为什么是equals,不能直接!=
            // 下面顺便安利一个小知识点~
            if(!list.get(left).equals(list.get(right)))
                return false;
            left++;
            right--;
        }
        return true;
    }

复杂度分析:
时间复杂度:, 循环遍历次数取决于链表的长度。
空间复杂度:, 使用了线性表的空间,空间大小取决于链表的长度。

Tips:
这里来说一下为什么上面的比较是equals而不是用运算符。细心的人应该会发现,ArrayList中的类型是Integer,是包装类型,而不是基本类型。我们直到包装类型都是对象,所以直接使用运算符进行比较的时候,如果不是同一个对象,那么它会直接返回false。但是这也不是一定的,因为在 Java 8 中,Integer 缓存池的大小默认为 -128~ 127。也就是说,如果你的Integer类型的数字范围在-128~ 127中,那么直接使用运算符进行比较,则它都回去Integer缓存池中找,所以能够直接比较里面的值。超过这个范围则每一次就会new一个新的包装类型出来,直接使用运算符则肯定会返回false。

方法二:利用栈的特性
因为如果链表是回文的,那么将整个链表反转后肯定还是跟原链表是一样的。所以我们就利用栈的先进后出的特性,将整个链表的节点放进栈中,然后进行出栈操作相当于链表反转的作用,再进行依次遍历比较。
图片说明

public boolean isPail (ListNode head) {

        if(head == null || head.next == null)
            return true;
        // 创建栈
        Stack<ListNode> stack = new Stack<>();
        ListNode node = head;
        // 将节点依次放进栈
        while(node != null){
            stack.push(node);
            node = node.next;
        }
        // 遍历然后依次比较
        while(head != null){
            // 如果中途发现不相等了,则直接返回false
            if(head.val != stack.pop().val)
                return false;
            head = head.next;
        }
        return true;
    }

复杂度分析:
时间复杂度:, 循环遍历次数取决于链表的长度。
空间复杂度:, 使用了栈,空间大小取决于链表的长度。

方法三:找中点+反转链表+遍历比较
看到方法的介绍其实就直到这个方法的步骤了,没错就是分为三个步骤!
1、快慢指针找中点

  • 先使用快慢指针找到链表的中点,然后根据中点找到表示后半段链表的头节点。

    可以利用 快慢指针,快指针一次走两步,慢指针依次走一步,当快指针走到终点的时候,此时如果链表的长度为偶数时,此时中间节点有两个,慢指针则走到了左端点。反之,慢指针则走到中间节点。(这两种情况在我们这道题目的总代吗,我们可以直接合并为一种,则第二个链表的长度比第一个链表的长度小1)

    class Solution {
    public ListNode middleNode(ListNode head) {
       if(head == null)
           return head;
       ListNode slow = head;
       ListNode fast = head;
       while(fast.next != null && fast.next.next != null){
           slow = slow.next;
           fast = fast.next.next;
       }
       if(fast.next == null)  // 长度为奇数
           return slow; // slow为中点
       else
           return slow.next;  // 长度为偶数  slow slow.next为中点
    }
    }

    2、反转链表 NC78 反转链表
    3、遍历比较

    public boolean isPail (ListNode head) {
    
       if(head == null || head.next == null)
           return true;
       // 慢指针
       ListNode slow = head; 
       // 快指针
       ListNode fast = head;
       while(fast != null && fast.next != null){
           fast = fast.next.next;
           slow = slow.next;
       }
       fast = slow.next; // 此时fast则会后半段链表的头结点
       slow.next = null; // 置为null
       ListNode nHead = null;
       while(fast != null){
           nHead = fast.next;
           fast.next = slow;
           slow = fast;
           fast = nHead;
       }
       nHead = slow; // 后半段链表反转后的链表
       fast = head;  // 原来的链表
       // 遍历判断是否是回文
       while (fast != null && nHead != null) {
           if (fast.val != nHead.val) {
               return false;
           }
           fast = fast.next;
           nHead = nHead.next;
       }
       return true;
    }
    
    

```
复杂度分析:
时间复杂度:, 循环遍历次数。
空间复杂度:, 没有使用额外的空间。

CS-Review 文章被收录于专栏

本专栏记录本人维护的仓库( cs-review.cn )分类刷题解法~

全部评论

相关推荐

牛客717484937号:双飞硕没实习挺要命的
点赞 评论 收藏
分享
昨天 13:08
蚌埠坦克学院 C++
服从性笔试吗,发这么多笔,现在还在发。
蟑螂恶霸zZ:傻 x 公司,发两次笔试,两次部门匹配挂,
投递金山WPS等公司10个岗位 >
点赞 评论 收藏
分享
3 1 评论
分享
牛客网
牛客企业服务