05 August 2008
Given a singly linked list, determine if it is a palindrome.
Example 1:
1
2
Input: 1->2
Output: false
Example 2:
1
2
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
这道题要求判断链表是否是回文的，跟Array相比链表没办法通过索引来读取后面的元素。首先可以用快慢指针来找到中点，在寻找重点过程中慢指针每走一步就把链表元素存入到一个stack中，当慢指针到达中点的时候就将存入到栈内的前半截元素和后半截进行比较；时间和空间都是O(n)，另外用递归的办法也是同样的复杂度。
其次如果想用O(n)的时间和O(1)的空间，那就在快慢指针找到中点的时候，将后半截链表元素进行翻转后再进行比较。
用Stack，先找到中点，把后半截的元素放入到stack中，根据stack后进先出的特点，从头开始比较，时空都是线性的
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
35
36
37
38
39
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
Stack<Integer> stack = new Stack<>();
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 如果是奇数个，slow这时候在正中间，如果是偶数个，slow这时候在中间偏左一个位置
slow = slow.next;
while (slow != null) {
stack.push(slow.val);
slow = slow.next;
}
slow = head;
while (!stack.isEmpty()) { //注意这里用iterator或者stream的forEach循环的话就是先进先出了，所以要用pop()
if (stack.pop() != slow.val) {
return false;
}
slow = slow.next;
}
return true;
}
}
用递归，这样就不用翻转链表后半截从而改变结构，做法是用一个索引index记录头结点，然后头递归到最后end，比较index和end的val，然后递归往上一层的同时挪动index到下一步，再进行比较，以此类推。这个做法比较简洁和锻炼递归思维，但空间是常数级的。
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode ref; //类变量保证两个methods都可以用同一个变量
public boolean isPalindrome(ListNode head) {
ref = head;
return checkPalindrome(head);
}
private boolean checkPalindrome(ListNode node) {
if (node == null) { //基线条件，null是回文
return true;
}
boolean dcResult = checkPalindrome(node.next); //头递归一直递归到最后一个结点后面的null，返回后到最后一个结点
if (ref.val != node.val) {//对比第一个结点和最后一个结点，每次递归将ref往后移动与递归本身同步
return false;
} else { // 当前对比相等，继续比较下一个元素
ref = ref.next;
}
return dcResult; //如果没有返回false，就看子递归返回的boolean值
}
}
翻转后半截链表进行比较
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
35
36
37
38
39
40
41
42
43
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
//先找到中点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
//倒转后半部分链表
ListNode last = slow.next;//如果是奇数个元素，slow会停在正中间那个元素处；如果是偶数个元素，slow会停在对半分前半截的最后一个位置；所以检查后半截链表的时候，从slow.next开始进行倒转
while (last.next != null) {
ListNode temp = last.next;
last.next = temp.next;
temp.next = slow.next;
slow.next = temp;
}
ListNode pre = head;//将一个指针重新指向前半截链表头部
//挨个比较
while (slow.next != null) {
slow = slow.next;
if (pre.val != slow.val) {
return false;
}
pre = pre.next;
}
return true;
}
}