随笔记录

算法-链表-是否为回文

2022-4-5 diaba 算法

package com.jiucaiyuan.net.algrithm.linked;

import java.util.Stack;

/**
 * 【问题】给定一个单项链表的头结点head，请判断该链表是否是回文结构
 * 【例子】
 * 1——>2——>1，返回true
 * 1——>2——>2——>1，返回true
 * 15——>6——>15，返回true
 * 1——>2——>3，返回false
 * 【要求】时间复杂度O(N)，空间复杂度O(1)
 * 【思路】快慢指针，快指针走到末尾，慢指针走到终点，终点之后遍历时，同时后半段给逆序，然后再遍历前半部分和后半部分，看是否一样
 *
 * @Author jiucaiyuan  2022/4/4 22:58
 * @mail services@jiucaiyuan.net
 */

public class IsPalindrome {
    /**
     * 使用额外n空间 栈
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        print(head);
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }

        while (head != null) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 使用n/2的额外空间 栈
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        print(head);
        if (head == null || head.next == null) {
            return true;
        }
        ListNode right = head.next;
        ListNode curr = head;
        while (curr.next != null && curr.next.next != null) {
            right = right.next;
            curr = curr.next.next;
        }
        Stack<ListNode> stack = new Stack<>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        while (!stack.isEmpty()) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 使用O(1)的额外空间
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome3(ListNode head) {
        print(head);
        if (head == null || head.next == null) {
            return true;
        }

        ListNode n1 = head;
        ListNode n2 = head;
        while (n2.next != null && n2.next.next != null) {  //find mid node
            n1 = n1.next;  //n1 to mid
            n2 = n2.next.next;  //n2 to end
        }

        //n1 开始逆序
        n2 = n1.next;   //n2 ——> right part first node
        n1.next = null;  //mid next ——> null
        ListNode n3 = null;
        while (n2 != null) {
            n3 = n2.next;   //n3——>save next node
            n2.next = n1;   //node of right to convert
            n1 = n2;
            n2 = n3;
        }

        //n1 和 n2 从两个链表的头开始处理，检查是否相同
        n3 = n1;  //n3 ——> save last node
        n2 = head; //n2——> left first node
        boolean res = true;
        while (n1 != null && n2 != null) {  // check palindrome
            if (n1.val != n2.val) {
                res = false;
                break;
            }
            n1 = n1.next;  //left to mid
            n2 = n2.next;  //right to mid
        }

        //恢复右半部分
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) {  //recover list
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(0);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        System.out.println(isPalindrome(head) + " vs " + isPalindrome2(head) + " vs " + isPalindrome3(head));

        ListNode head2 = new ListNode(0);
        ListNode node12 = new ListNode(1);
        ListNode node22 = new ListNode(1);
        ListNode node32 = new ListNode(0);
        head2.next = node12;
        node12.next = node22;
        node22.next = node32;

        System.out.println(isPalindrome(head2) + " vs " + isPalindrome2(head2) + " vs " + isPalindrome3(head2));

        ListNode head02 = new ListNode(0);
        ListNode node012 = new ListNode(1);
        ListNode node022 = new ListNode(2);
        ListNode node032 = new ListNode(0);
        head02.next = node012;
        node012.next = node022;
        node022.next = node032;
        System.out.println(isPalindrome(head02) + " vs " + isPalindrome2(head02) + " vs " + isPalindrome3(head02));
    }

    public static void print(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print("\t" + curr.val);
            curr = curr.next;
        }
        System.out.println();
    }
}