回文链表_Java

回文链表

题目描述：

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.*;


public class PalindromelinkedList {
        public static boolean isPalindrome(ListNode head) {
                //将所有的链表数据依次放入一个集合中；
                ArrayList 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 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

回文链表

Java相关栏目本月热门文章