题目:
对于一个链表, 请设计一个时间复杂度为 O(n), 额外空间复杂度为 O(1) 的算法, 判断其是否为回文结构.
给定一个链表的头指针 A, 请返回一个 bool 值, 代表其是否为回文结构. 保证链表长度小于等于 900.
测试样例:
输入: 1->2->2->1
返回: true
代码:(运行时间: 46 ms 占用内存: 10952K)
- import java.util.*;
- /*
- public class ListNode {
- int val;
- ListNode next = null;
- ListNode(int val) {
- this.val = val;
- }
- }*/
- public class PalindromeList {
- public boolean chkPalindrome(ListNode A) {
- Stack<Integer> stack = new Stack<>();
- boolean bool = false;
- if (A.next == null)
- return true;
- while(A.next != null)
- {// 只要没有判断出来是回文结构, 就一直进行判断, 直到遍历完整个链表
- if (bool == false)
- {
- stack.push(A.val);
- if (A.val == A.next.val)
- {// 做一个备份进行判断是否为回文结构
- bool = panduan(A,(Stack<Integer>) stack.clone());
- }
- }
- A = A.next;
- }
- return bool;
- }
- public boolean panduan(ListNode N ,Stack<Integer> stc) {
- while(true) {
- if (stc.isEmpty() && N.next == null)
- return true;
- else if (stc.isEmpty() || N.next == null)
- {
- return false;
- }
- else
- {// 只要从栈中出来的和数据和链表中对应的数据相等, 就一直循环.
- N = N.next;
- if (stc.pop() != N.val)
- return false;
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2583934.html