234. 回文链表 (JAVA)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了234. 回文链表 (JAVA)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含980字，纯文字阅读大概需要2分钟。

内容图文

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路：改变前半部分或者后半部分List的next指针。由于改变前半部分只需要一次遍历（用快、慢指针就能实现在第一次遍历的时候把前半部分的next指针反转）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head, pre = null, tmp;
        while(fast.next!=null) {
            fast = fast.next.next;
            tmp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = tmp;
            if(fast == null){ //双数
                return check(pre, slow);
            }
        }

        //单数
        return check(pre, slow.next);
    }

    private boolean check(ListNode l1, ListNode l2){
        if(l1 == null) return true;
        if(l1.val != l2.val) return false;
        return check(l1.next, l2.next);
    }
}

内容总结

以上是互联网集市为您收集整理的234. 回文链表 (JAVA)全部内容，希望文章能够帮你解决234. 回文链表 (JAVA)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端