Palindrome Linked List - LeetCode Daily Challenge

Problem Statement

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

Example

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

Try here before watching the video.

Video Explanation

Java Code

class Solution {
    private ListNode reverse(ListNode head) {
        ListNode prev, curr, next;
        prev = next = null;
        curr = head;

        while(curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }

    public boolean isPalindrome(ListNode head) {

        if(head == null || head.next == null) {
            return true;
        }

        ListNode slow, fast;
        slow = fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode head2 = reverse(slow);

        while(head2 != null) {
            if(head.val != head2.val) {
                return false;    
            }
            head = head.next;
            head2 = head2.next;
        }

        return true;
    }
}

class Solution {
private:
    ListNode* reverse(ListNode* head) {
        ListNode *prev, *curr, *next;
        prev = next = nullptr;
        curr = head;

        while (curr != nullptr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }

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

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

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

        ListNode *head2 = reverse(slow);

        while (head2 != nullptr) {
            if (head->val != head2->val) {
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }

        return true;
    }
};

Python Code

class Solution:
    def reverse(self, head):
        prev, curr, next = None, head, None
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

    def isPalindrome(self, head):
        if not head or not head.next:
            return True
        
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        head2 = self.reverse(slow)
        
        while head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        
        return True

Javascript Code

var isPalindrome = function(head) {
    const reverse = (head) => {
        let prev = null, curr = head, next = null;
        while (curr !== null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    };

    if (!head || !head.next) {
        return true;
    }

    let slow = head, fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let head2 = reverse(slow);

    while (head2 !== null) {
        if (head.val !== head2.val) {
            return false;
        }
        head = head.next;
        head2 = head2.next;
    }

    return true;
};

Go Code

func reverse(head *ListNode) *ListNode {
	var prev, curr, next *ListNode
	prev, curr, next = nil, head, nil

	for curr != nil {
		next = curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	var slow, fast *ListNode
	slow, fast = head, head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	head2 := reverse(slow)

	for head2 != nil {
		if head.Val != head2.Val {
			return false
		}
		head = head.Next
		head2 = head2.Next
	}

	return true
}

Complexity Analysis

Time Complexity: O(N)
1. Firstly, we iterate over the linked list using slow and fast pointers to find the middle node which takes almost N time.
2. Secondly, we are checking the equality of the node's values which takes almost N time.
Space Complexity: O(1), in the whole process we're not using any extra space.