LeetCode 234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

Solution:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode() : val(0), next(nullptr) {}
	* ListNode(int x) : val(x), next(nullptr) {}
	* ListNode(int x, ListNode *next) : val(x), next(next) {}
	* };
	*/
	class Solution {
	public:
	ListNode* reverse(ListNode* head){
	ListNode* pre = NULL;
	ListNode* cur = head;
	while(cur){
	auto n = cur->next;
	// reverse
	cur->next = pre;
	pre = cur;
	// update iteration
	cur = n;
	}
	return pre;
	}
	bool isPalindrome(ListNode* head) {
	int sz = 0;
	auto cur = head;
	while(cur){
	sz++;
	cur = cur->next;
	}
	// move to center
	int d = (sz + 1) / 2;
	cur = head;
	while(d){
	cur = cur->next;
	d--;
	}
	// reverse second half
	cur = reverse(cur);
	while(head and cur){
	if(head->val != cur->val)
	return false;
	head = head->next;
	cur = cur->next;
	}
	return true;
	}
	};

view raw 234-Palindrome-Linked-List.cpp hosted with ❤ by GitHub