234 Palindrome Linked List 回文链表
Description:
Given a singly linked list, determine if it is a palindrome.
Example:
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
题目描述:
请判断一个链表是否为回文链表。
示例：
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路:
- 用快慢指针找到链表的中点, 将中点以后的链表反转, 从开头和反转的链表比较即可
- 将链表里的数值取出转化为数值
时间复杂度O(n), 空间复杂度O(1)
代码:
C++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution
{
public:
bool isPalindrome(ListNode* head)
{
if (!head or !head -> next) return true;
ListNode *slow = head, *fast = head;
while (fast and fast -> next)
{
fast = fast -> next -> next;
slow = slow -> next;
}
ListNode* mid = NULL;
while (slow)
{
ListNode* p = slow -> next;
slow -> next = mid;
mid = slow;
slow = p;
}
while (head and mid)
{
if (head -> val != mid -> val) return false;
head = head -> next;
mid = mid -> next;
}
return true;
}
};
Java:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
int a = 0;
int b = 0;
int c = 0;
while (head != null) {
a *= 10;
a += head.val;
c *= 10;
if (c == 0) c = 1;
b += c * head.val;
head = head.next;
}
return a == b;
}
}
Python:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
a = b = c = 0
while head:
a *= 10
a += head.val
c *= 10
if not c:
c = 1
b += c * head.val
head = head.next
return a == b
