题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
http://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
运行时间:314ms超过84.62% 用Java提交的代码
占用内存:30336KB超过90.41%用Java提交的代码
- 利用快慢指针找到中间位置
链表长度为奇数指向中间位置,偶数指向中间靠右的结点
,同时将慢指针所指结点的值入栈 - 如果链表长度为奇数
fast != null
,慢指针指向下一个结点 - 慢指针指向的结点值与栈中元素一一比较
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
Stack<Integer> st = new Stack<Integer>();
ListNode slow = head;
ListNode fast = head;
if(fast.next == null) return true;
while(fast != null && fast.next != null){
st.push(slow.val);
slow = slow.next;
fast = fast.next.next;
}
if(fast != null){
slow = slow.next;
}
while(slow!=null){
if(slow.val == st.peek()){
slow = slow.next;
st.pop();
}else{
return false;
}
}
return true;
}
}