LeetCode Palindrome Linked List

LeetCode Palindrome Linked List

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

Follow up:
Could you do it in O(n) time and O(1) space?


本题要判断一个单向链表是否为回文链表。之前LeetCode Valid Palindrome判断的是数组,可以直接访问数组的头尾元素,但是链表不可以随机访问。

仔细观察一下,下面两条回文链表:

  1. 1->2->3->4->5->4->3->2->1
  2. 1->2->3->4->4->3->2->1

判断回文链表最原始的方法是从左往右读一遍和从右往左读一遍,如果读得的结果一样就是回文,比如第1条回文,从左往右是123454321,从右往左也是123454321,所以它是回文。

但是其实我们可以不用完整读一遍,我们只读一半就可以了,比如回文1的前半部分是1234,后半部分是4321,前半部分顺着读和后半部分倒着读都是1234,这样就足以说明是回文串了。

紧接着,对于链表,我们就有这样一种解题思路:首先找到链表的中间节点,然后把后半部分链表逆序,最后看看逆序的后半部分和顺序的前半部分是否相同。

找链表的中间节点的常规思路就是快慢指针,这个在很多题中都用到了,需要指出的是,回文链表有两种情况,一种是形如1的奇数个元素,另一种是形如2的偶数个元素。如果用快慢指针找中点,1能找到真正的中点5,2能找到前一个中点4,所以我们判断回文的时候,只需要把中点后面的链表逆序,然后只比较后半部分的链表元素。比如1的情况,逆序后半部分之后得到1->2->3->4,那么前半部分也只需要比较1->2->3->4,不需要比较5,因为这是奇数链表的中点,前后链表共享的元素;2的情况,逆序后半部分之后得到1->2->3->4,前半部分也是1->2->3->4,偶数长度的情况就会把中间的两个元素分到前后两部分。

完整代码如下:

class Solution {
public:
	bool isPalindrome(ListNode* head) {
		if (head == NULL || head->next == NULL)return true;
		ListNode *faster = head, *slower = head;
		while (faster->next != NULL&&faster->next->next != NULL) {
			faster = faster->next->next;
			slower = slower->next;
		}
		//bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
		ListNode *head2 = slower, *prior = slower->next, *tail;
		head2->next = NULL;
		while (prior != NULL) { // 逆序后半段链表
			tail = prior->next;
			prior->next = head2->next;
			head2->next = prior;
			prior = tail;
		}
		head2 = head2->next;
		while (head2 != NULL) {
			if (head->val != head2->val)return false;
			head = head->next;
			head2 = head2->next;
		}
		return true;
	}
};

本代码提交AC,用时25MS。

Leave a Reply

Your email address will not be published. Required fields are marked *