Leetcode-234 Palindrome Linked List

发表于 | 分类于 | 次

Palindrome Linked List

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

解题思路

先找到链表中点，用快慢指针；再将链表后半部分反转；最后遍历前后部分，查看两部分是否相同。

复杂度分析

  • 时间复杂度：$O(n)$，反转链表时间复杂度为 $O(n)$。
  • 空间复杂度：$O(1)$，反转链表空间复杂度为 $O(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
28
29
class Solution {
public:
	bool isPalindrome(ListNode* head) {
		ListNode *fast = head, *mid = head;
		while (fast) { //找中点
			fast = fast->next;
			if (fast) {
				fast = fast->next;
				mid = mid->next;
			}
		}
		//反转后半部分
		ListNode *pre = nullptr;
		while (mid) {
			ListNode *tmp = mid->next;
			mid->next = pre;
			pre = mid;
			mid = tmp;
		}
		//查看前后部分是否相同
		ListNode *front = head, *back = pre;
		while (front && back) {
			if (front->val != back->val) return false;
			front = front->next;
			back = back->next;
		}
		return true;
	}
};