判断链表是否为回文结构的三种方法

import java.util.Stack;

public class test10 {
    // 定义一个Node类，用于链表节点
    public static class Node{
        public int value; // 节点的值
        public Node next; // 指向下一个节点的引用

        // 构造函数，初始化节点的值
        public Node(int data){
            this.value = data;
        }
    }

    // 方法1：使用栈来判断链表是否为回文结构
    public static boolean isPalindrome1(Node head){
        Stack<Node> stack = new Stack<Node>(); // 创建一个栈来存储链表节点
        Node cur =head; // 从头节点开始遍历链表
        while (cur!=null){

// 遍历链表，将所有节点压入栈中
            stack.push(cur);
            cur = cur.next;
        }
        while(head !=null){

// 再次从头节点开始遍历链表
            if(head.value != stack.pop().value){

// 如果当前节点的值与栈顶节点的值不相等，说明不是回文结构
                return false;
            }
            head = head.next; // 继续遍历下一个节点
        }
        return true; // 如果所有节点都满足回文条件，返回true
    }

    // 方法2：优化方法1，减少空间复杂度
    public static boolean isPalindrome2(Node head){
        if(head == null || head.next == null){

// 如果链表为空或只有一个节点，直接返回true
            return true;
        }
        Node right = head.next; // 定义快慢指针中的快指针
        Node cur = head; // 定义快慢指针中的慢指针
        while (cur.next != null && cur.next.next != null){

// 快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表末尾
            right = right.next;
            cur = cur.next.next;
        }
        Stack<Node> stack = new Stack<Node>(); // 创建一个栈来存储后半部分链表的节点
        while(right != null){

// 将后半部分链表的节点压入栈中
            stack.push(right);
            right = right.next;
        }
        while(!stack.isEmpty()){ // 从栈中弹出节点并与前半部分链表进行比较
            if(head.value != stack.pop().value){ // 如果节点值不相等，说明不是回文结构
                return false;
            }
            head = head.next; // 继续比较下一个节点
        }
        return true; // 如果所有节点都满足回文条件，返回true
    }

    // 方法3：不使用额外的空间，通过反转链表的一半来实现
    public static boolean isPalindrome3(Node head){
        if(head == null || head.next ==null){

// 如果链表为空或只有一个节点，直接返回true
            return true;
        }
        Node n1 = head; // 定义快慢指针中的慢指针
        Node n2 = head; // 定义快慢指针中的慢指针
        while(n2.next !=null && n2.next.next != null){

// 快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表末尾
            n1 = n1.next;
            n2 = n2.next.next;
        }
        n2 =  n1.next; // n2指向链表的中间位置
        n1.next = null; // 断开链表，使得后半部分成为一个新的链表
        Node n3 = null; // 定义一个临时节点，用于反转后半部分链表

        while (n2 != null){

// 反转后半部分链表
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }
        n3 = n1; // n3指向反转后的链表头节点
        n2 = head; // n2重新指向原链表的头节点
        boolean res = true; // 默认结果为true
        while (n1 != null && n2 != null){

// 比较反转后的链表和原链表的前半部分
            if(n1.value != n2.value){

// 如果节点值不相等，说明不是回文结构
                res =false;
                break;
            }
            n1 = n1.next; // 继续比较下一个节点
            n2 = n2.next;
        }
        n1 = n3.next; // n1指向反转后的链表的第二个节点
        n3.next = null; // 恢复原链表的结构
        while(n1 != null){

// 再次反转后半部分链表，恢复原链表的结构
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res; // 返回最终的结果
    }
}
 

原文地址：https://blog.csdn.net/2401_83010439/article/details/140596164

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！