[数据结构与算法]回文链表_使用栈数据结构来解决

题目描述：?

234. 回文链表

难度简单1137

给你一个单链表的头节点?head?，请你判断该链表是否为回文链表。如果是，返回?true?；否则，返回?false?。

力扣

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105]?内
• 0 <= Node.val <= 9

进阶：你能否用?O(n)?时间复杂度和?O(1)?空间复杂度解决此题？

解题思路：

使用栈这种数据结构来判断是否为回文链表；

将集合的前一半依次顺序存入栈中；

将栈中的元素再进行出栈，如果出栈之后的元素顺序与集合的后一半一样的话，则说明是回文链表，否则不是；

代码：

package zyh.springcloud.chapter2.service.impl.datastructure.stack;

import java.util.*;

/**
 * @ClassName PalindromeLinkedList
 * @Author zhangyonghui
 * @Description：回文链表
 * @Date 2021/10/3 16:55
 * @Version 1.0
 **/
public class PalindromeLinkedList {
        public static boolean isPalindrome(ListNode head) {
                //将所有的链表数据依次放入一个集合中；
                ArrayList<Integer> arrayList = new ArrayList<>();
                arrayList.add(head.val);
                while (head.next != null) {
                        arrayList.add(head.next.val);
                        head=head.next;
                }
                System.out.println("打印一下集合中的元素 = " + arrayList);
                if(arrayList.size()==1){
                        return true;
                }
                //使用栈这种数据结构来判断是否为回文链表；
                //将集合的前一半依次顺序存入栈中；
                //将栈中的元素再进行出栈，如果出栈之后的元素顺序与集合的后一半一样的话，则说明是回文链表，否则不是；

                //新建一个栈：
                Deque<Integer> stack = new LinkedList<>();

                //将集合的前一半存入栈中：
                for (int i = 0; i < arrayList.size() / 2; i++) {
                        stack.push(arrayList.get(i));
                }

                int iTemp = 0;
                if (arrayList.size() % 2 == 0) {
                        iTemp = arrayList.size() / 2;
                }else{
                        iTemp=arrayList.size()/2+1;
                }
                //将出栈之后的元素与集合的后一半进行对比：
                for (int i=iTemp; i <arrayList.size(); i++) {
                        //取栈顶元素：
                        Integer pop = stack.pop();
                        if (!arrayList.get(i).equals(pop)) {
                                return false;
                        }
                }
                return true;
        }


        /**
         * 测试：
         * @param args
         */
        public static void main(String[] args) {
                ListNode listNode3 = new ListNode(1);
                ListNode listNode2 = new ListNode(2, listNode3);
                ListNode listNode1 = new ListNode(2,listNode2);
                ListNode listNode = new ListNode(1, listNode1);
                boolean palindrome = isPalindrome(listNode);
                System.out.println("是否是回文链表 = " + palindrome);
        }

}