Linked List Palindrome Editorial

Practice Problem Link: Linked List Palindrome

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a non-negative number represented as a linked list, determine whether it is a palindrome or not.

Approach

The idea is to compare the two halves of the linked list.

• Get the middle element of the linked list
• Reverse the second half of the linked list and compare it with the first half.
• If both the halves are equal then return true otherwise return false.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* getMiddleNode(ListNode* head) {
	ListNode* front = head;
	while (front->next != NULL && front->next->next != NULL) {
		head = head->next;
		front = front->next->next;
	} 
	return head;
}
ListNode* reverse (ListNode *head) {
	ListNode *prevNode = NULL;
	ListNode *nextNode;
	while (head->next != NULL) {
		nextNode = head->next;
		head->next = prevNode;
		prevNode = head;
		head = nextNode;
	} 
	head->next = prevNode;
	return head;
}
bool isPalindrome(ListNode* list) {
    ListNode* middleNode = getMiddleNode(list);
	ListNode *secondHalf = reverse(middleNode->next);
	while(secondHalf != NULL) {
		if(secondHalf->data != list->data) {
			return false;
		}
		secondHalf = secondHalf->next;
		list = list->next;
	}
	return true;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode getMiddleNode(ListNode head) {
		ListNode front = head;
		while (front.next != null && front.next.next != null) {
			head = head.next;
			front = front.next.next;
		} 
		return head;
	}
	ListNode reverse (ListNode head) {
		ListNode prevNode = null;
		ListNode nextNode;
		while (head.next != null) {
			nextNode = head.next;
			head.next = prevNode;
			prevNode = head;
			head = nextNode;
		} 
		head.next = prevNode;
		return head;
	}
	boolean isPalindrome(ListNode list) {
	    ListNode middleNode = getMiddleNode(list);
		ListNode secondHalf = reverse(middleNode.next);
		while(secondHalf != null) {
			if(secondHalf.data != list.data) {
				return false;
			}
			secondHalf = secondHalf.next;
			list = list.next;
		}
		return true;
	}
}