234. Palindrome Linked List

1. 原始题目

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

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

2. 题目理解

判断给定链表是否为回文。即正反节点数字一样。例如1234321，无论正反都是这个。就是对称。

坑：空链表和单元素链表都是回文！

3. 解题

思路有两个：特性一：关于中间元素对称。所以还是快慢指针，慢指针边走边将元素入栈，快指针每次走两步。当快指针走到末尾时，慢指针正好在中间。然后此时开始出栈。慢指针边走边和出栈的元素比较。若有不同则非回文。这里需要稍稍考虑指针的位置，因为可能回文是奇数或偶数。

解法：

 1 class Solution:
 2     def isPalindrome(self, head: ListNode) -> bool:
 3         if not head:        # 空链表为回文
 4             return True
 5         if not head.next:   # 单元素为回文
 6             return True
 7         pre = ListNode(0)   # 快指针
 8         pre.next = head
 9         cur = pre           # 慢指针
10         stack = []
11         while pre and pre.next:    
12             cur = cur.next         
13             stack.append(cur.val)      # 慢指针边走边入栈
14             pre = pre.next           
15             pre = pre.next             # 快指针没事走两步
16             
17         if pre:            
18             cur = cur.next             # 对于偶数项回文，慢指针需多走一步
19                 
20         while(cur):                    # 出栈和慢指针比较 
21             if(cur.val!=stack.pop()):  # 一有不同即为False
22                 return False
23             cur = cur.next
24         return True

验证：

1 listnode1 = ListNode_handle(None)
2 s1 = [1,2,3,666,3,2,1]
3 for i in s1:
4     listnode1.add(i)
5 listnode1.print_node(listnode1.head)
6 
7 s = Solution()
8 head = s.isPalindrome(listnode1.head)
9 print(head)

1 2 3 666 3 2 1
True

思路2：回文正序和逆序一样:

1 class Solution:
2     def isPalindrome(self, head: ‘ListNode‘) -> ‘bool‘:
3         values = []       # values保存正序
4         
5         while head:
6             values.append(head.val)
7             head = head.next
8             
9         return values == values[::-1]     # 正序和逆序比较