234. 回文链表

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 516 阅读时长 ≈ 2 分钟

考点

  • 快慢指针/双指针
  • 链表的反转

题解

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
class Solution {
	private:
		bool judgeFunc(ListNode* head, ListNode* midNode) {
			for (ListNode *left = head, *right = midNode->next; right != nullptr; left = left->next, right = right->next) {
				if (left->val != right->val) return false;
			}
			return true;
		}

		ListNode* reverseList(ListNode* dummyHead) {
			ListNode *tail = dummyHead->next;
			while (tail->next != nullptr) {
				ListNode *node = tail->next;
				tail->next = node->next;
				node->next = dummyHead->next;
				dummyHead->next = node;
			}
			return dummyHead;
		}

		ListNode* findMid(ListNode* head) {
			ListNode *slow = head, *fast = head;
			while (fast->next != nullptr && fast->next->next != nullptr) {
				slow = slow->next;
				fast = fast->next->next;
			}
			return slow;
		}

	public:
		bool isPalindrome(ListNode* head) {
			if (head->next == nullptr) return true;
			return (judgeFunc(head, reverseList(findMid(head))));
		}
};

思路

验证回文串，最直接的方法就是双指针，左指针从头向尾遍历，右指针从尾向头遍历，只要两个指针指向的值不一样就肯定不是回文串

  1. 子问题：两个指针反向遍历，比较两个指针指向的值

  2. 递归语句顺序：递归方向分为一去一回，去方向到达临界点后返回；这里只能在回方向操作，因为右指针需要从尾向头遍历

    左指针怎么办呢？额外单独设置一个成员变量即可，待右指针开始从尾向头遍历时再做比较

  3. 返回值：不需要返回值

  4. 临界点：右指针为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
	private:
		bool ans;
		ListNode *left;
		void recursiveFunc(ListNode *right) {
			if (right == nullptr) return;
			recursiveFunc(right->next);
			if(left->val != right->val) ans = false;
			left = left->next;
		}

	public:
		bool isPalindrome(ListNode* head) {
			left = head;
			ans = true;
			recursiveFunc(head);
			return ans;
		}
};

但题目要求只能以常数空间复杂度运行，故而不能使用递归；用迭代分为以下几个步骤

  1. 找到链表中心点，分为左、右两个子链表
  2. 右子链表反转
  3. 即可对左、右两个子链表进行同向比较了

这里有一个可有可无的Trick

如果是奇数个链表节点，比如{1, 2, 3, 4, 5}，找到的链表中心点是3

如果是偶数个链表节点，比如{1, 2, 3, 4}，则找到的链表中心点应为2

这样中心点就可以作为右子链表的dummyHead，便于反转