Leetcode Answers 234

接着刷题,又是一道Easy题,还是和回文有关的。

题目:
Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

思路:
判断一个LinkedList是不是回文,主要就是想看如果不能用两个pointer从两端向中间查找可以怎么弄。那么可以考虑折半的方法,用stack装前半段,然后如果是奇数跳过最中间的,然后后半段开始和stack.pop()作对比,差一个就返回false,都看过了就返回true。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public bool IsPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
int len = 0;
ListNode n = head;
while(n!=null){
len++;
n = n.next;
}
n = head;
Stack<int> stk = new Stack<int>();
int t = 1;
while(t <= len / 2){
stk.Push(n.val);
n = n.next;
t++;
}
if(len % 2 > 0) n = n.next;
while(n!=null){
if(stk.Pop() != n.val) return false;
n = n.next;
}
return true;
}
}

以上。

17-04-25
@Sturbridge