厚积薄发打卡Day109:链表(七)回文链表

厚积薄发打卡Day109:链表(七)回文链表,第1张

厚积薄发打卡Day109:链表(七)回文链表 厚积薄发打卡Day109:链表(七)<回文链表> 回文链表

问题:如何判断一个链表是不是回文?要求解法的时间复杂度是O(m),并且不得使用超过 O(1)的辅助空间。如果一个链表是回文,那么链表的节点序列从前往后看和从后往前看是相同的。例如,链表A的节点序列从前往后看和从后往前看都是 1、2、3、3、2、1,因此这是一个回文链表。

链表A:1->2->3->3->2->1

思路
  1. 对半分
  2. 反转
  3. 比较
实现
public class PalindromeNode {

    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode secondHalf = slow.next;
        if (fast.next != null) {
            secondHalf = slow.next.next;
        }
        slow.next = null;
        return equal(secondHalf, ReverseNodeList.reverseNodeList(head));
    }

    private static boolean equal(ListNode head1, ListNode head2) {
        while (head1 != null && head2 != null) {
            if (head1.val != head2.val) {
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return head1 == null && head2 == null;
    }


    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(2);
        ListNode node6 = new ListNode(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        ListNode.printNodeList(node1);
        System.out.println(isPalindrome(node1));
    }
}
1->2->3->3->2->1->NULL
true

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5687040.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存