判断一个链表是否为回文结构（Java实现）

川长思鸟来 2021-12-18 08:23 276阅读 0赞

这个算法题意思很容易理解，就是一个链表的顺序和它反过来的顺序是一样的则是回文结构，否则不是。比如：1->2->3->2->1，链表结构反过来也是1->2->3->2->1，这就是回文结构，而1->2->3->2，反过来就是2->3->2->1，就不是回文结构。

简单粗暴的做法就是：将链表反转生成一个新的链表，然后依次比较两个链表的每一个元素，如果均相等则是回文结构。这里我们可以不用反转链表，而是借助一个栈，将链表的数据全部压入栈中，然后从栈顶依次取出元素和原链表头部取出元素比较。栈的特点是先进后出，正好可以构成一个反转的链表。

这个算法的代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

根据回文结构的特点，链表前半部分和后半部分反转之后顺序是一致的，所以可以考虑不用反转整个链表，而是后半部分。要找到后半部分，需要两个指针，他们都从头部开始遍历，一个指针遍历的速度是另一个指针的两倍，这样，当快的指针遍历完成的时候，慢的指针位置就正好是中间位置。再把中间位置到链表尾部的所有节点放入一个堆栈，构成一个反转的链表，后面的判断就回到第一个办法的判断了。

代码如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1][]

判断链表的节点和栈顶弹出的节点数据是否相等，两个方法是一样的。

这里给出完整的代码：

Node.java

package com.xxx.algorithm.search;
    
    public class Node {
    	int data;
    	Node next;
    	public Node(int data){
    		this.data = data;
    	}
    }

LinkedList.java

package com.xxx.algorithm.search;
    public class LinkedList {
    	Node head;
    	public void insert(int data){
    		Node node = new Node(data);
    		if(head==null){
    			head = node;
    		}else{
    			Node curNode = head;
    			while(curNode.next!=null){
    				curNode = curNode.next;
    			}
    			curNode.next = node;
    		}
    	}
    	
    }

Palindrom.java

package com.xxx.algorithm.search;
    
    import java.util.Stack;
    /***
     * 判断链表结构是否是回文
     * 回文的特点：链表中的节点顺序和反过来的节点顺序是一样的
     * 例如 1->2->3->2->1 反过来也是  1->2->3->2->1
     */
    public class Palindrom {
    	
    	//这种判断方式是借助一个栈，从链表头部依次遍历，将节点压入栈中
    	//接着比较链表头部和栈中弹出的每一个节点数据是否相等
    	public static boolean isPalindrom(Node head){
    		Stack<Node> stack = new Stack<Node>();
    		Node cur = head;
    		while(cur!=null){
    			stack.add(cur);
    			cur = cur.next;
    		}
    		while(head!=null){
    			if(head.data!=stack.pop().data)
    				return false;
    			head = head.next;
    		}
    		return true;
    	}
    	
    	//链表结构如果是回文，那么从链表头部到链表中间和从链表尾部到中间的节点顺序应该也是一样的
    	//思路是找到链表中间的节点位置，然后依次压入栈中
    	//再来比较链表头部元素和栈中弹出的元素是否相等
    	public static boolean ispalindrom(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.data!=stack.pop().data){
    				return false;
    			}
    			head = head.next;
    		}
    		return true;
    	}
    	
    	
    	
    	public static void main(String[] args) {
    		LinkedList list = new LinkedList();
    		list.insert(1);
    		list.insert(2);
    		list.insert(4);
    		list.insert(3);
    		list.insert(5);
    		list.insert(3);
    		list.insert(4);
    		list.insert(2);
    		list.insert(1);
    		System.out.println("isPalindrom:"+isPalindrom(list.head));
    		System.out.println("ispalindrom:"+ispalindrom(list.head));
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: /images/20211218/350232ea2f204f1490f93b9b7562d774.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1]: /images/20211218/4442b65933624128bf60c2d1ae5b5760.png