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

╰+攻爆jí腚メ 2022-06-05 07:55 324阅读 0赞

【题目】  
　　给定一个链表的头结点head，请判断该链表是否为回文结构  
　　例如：  
　　1->2->1 返回true  
　　1->2->3 返回false

【代码】  
　　演示三种方法

import java.util.*;
    
    
    
    class test{ 
        class Node{
            public Node head;
            public int value;
            public Node next;
    
            public Node(int data){
                this.value = data;
            }
        }
        public static boolean isPalindrom1(Node head){
            if(head==null||head.next==null){
                return true;
            }
            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;
        }
    
        public static boolean isPalindrom2(Node head){
            if(head==null||head.next==null){
                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;
        }
    
        public static boolean isPalindrom3(Node head){
            if(head==null || head.next==null){
                return true;
            }
            Node n1 = head;
            Node n2 = head;
            while(n2.next!=null&&n2.next.next!=null){
                n1 = n1.next;
                n2 = n2.next.next;
            }
            Node n3 = n1.next;
            n1.next = null;
            while(n3!=null){
                n2 = n3.next;
                n3.next = n1;
                n1 = n3;
                n3 = n2;
            }
            n3 = n1;
            while(head.next!=null){
                if(head.value!=n1.value){
                    return false;
                }
                head = head.next;
                n1 = n1.next;
            }
            n1 = n3.next;
            while(n3!=null){
                n2 = n1.next;
                n1.next = n3;
                n1 = n2;
                n3 = n1.next;
            }
            return true;
        }
    }