In this post, we are going to solve the 234. Palindrome Linked List problem of Leetcode. This problem 234. Palindrome Linked List is a Leetcode easy level problem. Let’s see the code, 234. Palindrome Linked List – Leetcode Solution.

Problem

Given the head of a singly linked list, return true if it is a palindrome.

Example 1 :

Input: head = [1,2,2,1]
Output: true

Example 2 :

Input: head = [1,2]
Output: false

Constraints

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Now, let’s see the code of 234. Palindrome Linked List – Leetcode Solution.

Palindrome Linked List – Leetcode Solution

234. Palindrome Linked List – Solution in Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null) return head;
        
        ListNode curr = head, prev = null;
        while(curr != null){
            ListNode forw = curr.next;
            curr.next = prev;
            prev = curr;
            curr = forw;
        }
        return prev;
    }
    
    public ListNode getMidNode(ListNode head){
        
        if(head == null || head.next == null)return head;
        
        ListNode curr = head;
        ListNode mid = head;
        while(curr.next != null && curr.next.next != null){
            curr = curr.next.next;
            mid = mid.next;
        }
        return mid;
    }
    
    public boolean isPalindrome(ListNode head) {
        
        ListNode mid = getMidNode(head);
        ListNode halfList = reverse(mid.next);
        ListNode curr = head;
        
        while(halfList != null){
            if(curr.val != halfList.val) return false;
            curr = curr.next;
            halfList = halfList.next;
        }
        
        return true;
        
    }
}

234. Palindrome Linked List – Solution in C++

/**
 * 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* ptr) 
     {
        ListNode* pre=NULL;
        ListNode* nex=NULL;
        while(ptr!=NULL) {
            nex = ptr->next;
            ptr->next = pre;
            pre=ptr;
            ptr=nex;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        if(head==NULL||head->next==NULL) return true;

        ListNode* slow = head;
        ListNode* fast = head;

        while(fast->next!=NULL&&fast->next->next!=NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }

        slow->next = reverse(slow->next);
        slow = slow->next;
        ListNode* dummy = head;

        while(slow!=NULL) {
            if(dummy->val != slow->val) return false;
            dummy = dummy->next;
            slow = slow->next;
        }
        return true;
    }
};

234. Palindrome Linked List – Solution in Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	def isPalindrome(self, head: Optional[ListNode]) -> bool:

		fast = head
		slow = head

		#Finding the Mid of the linked list
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next

		# Reversing the second half of the linked list
		node = None
		while slow:
			n = slow.next
			slow.next = node
			node = slow
			slow = n

		# Comparing the First and the Second Half
		while node:
			if node.val != head.val:
				return False
			node = node.next
			head = head.next

		return True

        

Note: This problem 234. Palindrome Linked List is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.