Grow your way forward, through the triumphs and the setbacks. 在胜利与挫折的交错中不断成长。 问题描述 请判断一个链表是否为回文链表。链表为单向无环链表 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 反转后半部分链表 这题是让判断链表是否是回文链表，所谓的回文链表就是以链表中间为中心点两边对称。我们常见的有判断一个字符串是否是回文字符串，这个比较简单，可以使用两个指针，一个最左边一个最右边，两个指针同时往中间靠，判断所指的字符是否相等。 但这题判断的是链表，因为这里是单向链表，只能从前往后访问，不能从后往前访问，所以使用判断字符串的那种方式是行不通的。但我们可以通过找到链表的中间节点然后把链表后半部分反转（关于链表的反转可以看下432，剑指 Offer-反转链表的3种方式），最后再用后半部分反转的链表和前半部分一个个比较即可。这里以示例2为例画个图看一下。
最后再来看下代码
1public boolean isPalindrome(ListNode head) {
2 ListNode fast = head, slow = head;
3 //通过快慢指针找到中点
4 while (fast != null && fast.next != null) {
5 fast = fast.next.next;
6 slow = slow.next;
7 }
8 //如果fast不为空，说明链表的长度是奇数个
9 if (fast != null) {
10 slow = slow.next;
11 }
12 //反转后半部分链表
13 slow = reverse(slow);
14
15 fast = head;
16 while (slow != null) {
17 //然后比较，判断节点值是否相等
18 if (fast.val != slow.val)
19 return false;
20 fast = fast.next;
21 slow = slow.next;
22 }
23 return true;
24}
25
26//反转链表
27public ListNode reverse(ListNode head) {
28 ListNode prev = null;
29 while (head != null) {
30 ListNode next = head.next;
31 head.next = prev;
32 prev = head;
33 head = next;
34 }
35 return prev;
36}
使用栈解决
我们知道栈是先进后出的一种数据结构，这里还可以使用栈先把链表的节点全部存放到栈中，然后再一个个出栈，这样就相当于链表从后往前访问了，通过这种方式也能解决，看下代码
1public boolean isPalindrome(ListNode head) {
2 ListNode temp = head;
3 Stack<Integer> stack = new Stack();
4 //把链表节点的值存放到栈中
5 while (temp != null) {
6 stack.push(temp.val);
7 temp = temp.next;
8 }
9
10 //然后再出栈
11 while (head != null) {
12 if (head.val != stack.pop()) {
13 return false;
14 }
15 head = head.next;
16 }
17 return true;
18}
这里相当于链表从前往后全部都比较了一遍，其实我们只需要拿链表的后半部分和前半部分比较即可，没必要全部比较，所以这里可以优化一下
1public boolean isPalindrome(ListNode head) {
2 if (head == null)
3 return true;
4 ListNode temp = head;
5 Stack<Integer> stack = new Stack();
6 //链表的长度
7 int len = 0;
8 //把链表节点的值存放到栈中
9 while (temp != null) {
10 stack.push(temp.val);
11 temp = temp.next;
12 len++;
13 }
14 //len长度除以2
15 len >>= 1;
16 //然后再出栈
17 while (len-- >= 0) {
18 if (head.val != stack.pop())
19 return false;
20 head = head.next;
21 }
22 return true;
23}
递归方式解决
我们知道，如果对链表逆序打印可以这样写
1private void printListNode(ListNode head) {
2 if (head == null)
3 return;
4 printListNode(head.next);
5 System.out.println(head.val);
6}
也就是说最先打印的是链表的尾结点，他是从后往前打印的，看到这里是不是有灵感了，我们来对上面的对面进行改造一下
1ListNode temp;
2
3public boolean isPalindrome(ListNode head) {
4 temp = head;
5 return check(head);
6}
7
8private boolean check(ListNode head) {
9 if (head == null)
10 return true;
11 boolean res = check(head.next) && (temp.val == head.val);
12 temp = temp.next;
13 return res;
14}
问题分析
回文链表的判断，相比回文字符串的判断稍微要麻烦一点，但难度也不是很大，如果对链表比较熟悉的话，这3种解决方式都很容易想到，如果不熟悉的话，可能最容易想到的就是第2种了，也就是栈和链表的结合。
如果对栈和链表不熟悉的话，可以看下352，数据结构-2,链表，这里详细介绍了单向链表，双向链表，以及环形链表的断开和连接。也可以看下363，数据结构-4,栈，这里有对栈的一些简单介绍和实例讲解。
联系客服
