Palindrome : Implement a function to check if a linked list is a palindrome.
这种题目的话应该是不允许使用类似的数据结构来替代的，比如用ArrayList，但是可以用其他数据结构比如HashMap、Stack。
解法1
克隆一个反向链表，然后遍历比较：
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
public boolean isPalindrome ( Node node ) {
Node reverse = reverseAndClone ( node );
return isEqual ( node , reverse );
}
// 反向clone一个链表是通过不断在head插入克隆的元素来做到
Node reverseAndClone ( Node node ) {
Node head = null ;
while ( node != null ) {
Node clone = new Node ( node . data );
clone . next = head ;
head = clone ;
node = node . next ;
}
return head ;
}
boolean isEqual ( Node a , Node b ) {
while ( a != null && b != null ) {
if ( a . data != b . data ) {
return false ;
}
a = a . next ;
b = b . next ;
}
return true ;
}
解法2
用递归+Stack的方式来判断是否回文。比如在中间节点之前在Stack中push，过了中间节点则开始判断是否对称。已知链表长度：
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
public boolean isPalindrome ( Node node , int index , int length , Stack stack ) {
boolean odd = length % 2 == 1 ;
int mid = length / 2 ;
if ( odd ) {
if ( index < mid ) {
stack . push ( node . data );
} else if ( index > mid ) {
Object top = stack . pop ();
if ( ! top . equals ( node . data )) {
return false ;
}
}
} else {
if ( index < mid ) {
stack . push ( node . data );
} else if ( index >= mid ) {
Object top = stack . pop ();
if ( ! top . equals ( node . data )) {
return false ;
}
}
}
if ( node . next != null ) {
return isPalindrome ( node . next , index + 1 , length , stack );
}
return true ;
}
解法3
上面这个用递归似乎多余了，可以用循环来做：
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
public boolean isPalindrome ( Node node , int length ) {
int index = 0 ;
int mid = length / 2 ;
boolean odd = length % 2 == 1 ;
Stack < Integer > stack = new Stack <> ();
while ( node != null ) {
if ( odd ) {
if ( index < mid ) {
stack . push ( node . data );
} else if ( index > mid ) {
Integer top = stack . pop ();
if ( top . intValue () != node . data ) {
return false ;
}
}
} else {
if ( index < mid ) {
stack . push ( node . data );
} else if ( index >= mid ) {
Integer top = stack . pop ();
if ( top . intValue () != node . data ) {
return false ;
}
}
}
node = node . next ;
index ++ ;
}
return true ;
}
解法4
如果不知道链表的长度怎么弄？可以用快慢两个指针，慢指针每次走一步，快指针每次走两步，在快指针走到尾之前往Stack里push，到尾之后Stack里pop，看看是不是一样。
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
public boolean isPalindrome ( Node node ) {
Node slow = node ;
Node fast = node ;
Stack stack = new Stack ();
boolean odd = false ;
while ( fast != null ) {
stack . push ( slow . data );
slow = slow . next ;
fast = fast . next ;
if ( fast == null ) {
odd = true ;
break ;
}
fast = fast . next ;
}
if ( odd ) {
// pop middle element
stack . pop ();
}
while ( slow != null ) {
Object top = stack . pop ();
if ( ! top . equals ( slow . data )) {
return false ;
}
slow = slow . next ;
}
if ( ! stack . isEmpty ()) {
return false ;
}
return true ;
}
评论