Palindrome Linked List

🏠 ⬅️ ➡️

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

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

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

Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
⚠️ Correct 
program palindrome_list
    implicit none

    type :: node
        integer :: val
        type(node), pointer :: next => null()
    end type

    type(node), pointer :: head

    logical :: result

    call test_example1()
    call test_example2()

contains

    subroutine test_example1()
        type(node), pointer :: curr
        allocate(curr)
        curr%val = 1
        curr%next => curr
        allocate(curr%next)
        curr%next%val = 2
        curr%next%next => curr
        allocate(curr%next%next)
        curr%next%next%val = 2
        curr%next%next%next => curr
        allocate(curr%next%next%next)
        curr%next%next%next%val = 1
        curr%next%next%next%next => null()
        result = is_palindrome(head)
        write (*, '(A, L1)') 'Example 1: ', result
    end subroutine

    subroutine test_example2()
        type(node), pointer :: curr
        allocate(curr)
        curr%val = 1
        curr%next => curr
        allocate(curr%next)
        curr%next%val = 2
        curr%next%next => null()
        result = is_palindrome(head)
        write (*, '(A, L1)') 'Example 2: ', result
    end subroutine

    function is_palindrome(head) result(result_)
        type(node), pointer, intent(in) :: head
        type(node), pointer :: slow, fast
        logical :: result_

        slow => head
        fast => head
        do while (associated(fast))
            if (.not. associated(fast%next)) exit
            fast => fast%next%next
            slow => slow%next
        end do

        result_ = .true.
        do while (associated(slow))
            if (slow%val /= fast%val) then
                result_ = .false.
                exit
            end if
            slow => slow%next
            fast => fast%next
        end do
    end function

end program
❌ Compiled
❌ Executed
❌ Correct 
module palindrome_list

implicit none

type :: node
    integer :: val
    type(node), pointer :: next => null()
end type node

interface
    function is_palindrome(head) result(is_palindrome)
        type(node), pointer, intent(in) :: head
        logical :: is_palindrome
    end function is_palindrome
end interface

contains

function is_palindrome(head) result(is_palindrome)
    type(node), pointer, intent(in) :: head
    type(node), pointer :: slow, fast
    integer :: length, mid, i
    logical :: is_palindrome

    ! Find the length of the list
    length = 0
    do
        length = length + 1
        if (.not. associated(head%next)) exit
        head => head%next
    end do

    ! Find the middle of the list
    mid = length / 2 + 1

    ! Reverse the second half of the list
    slow => head
    do i = 1, mid - 1
        fast => slow%next
        slow%next => fast%next
        fast%next => slow
    end do

    ! Check if the first and second halves are the same
    is_palindrome = .true.
    do i = 1, mid
        if (head%val /= slow%val) then
            is_palindrome = .false.
            exit
        end if
        head => head%next
        slow => slow%next
    end do

end function is_palindrome

end module palindrome_list

program test
    use palindrome_list
    implicit none

    ! Examples
    type(node), pointer :: head
    head => null()
    call add_node(head, 1)
    call add_node(head, 2)
    call add_node(head, 2)
    call add_node(head, 1)
    write (*,*) is_palindrome(head)

    head => null()
    call add_node(head, 1)
    call add_node(head, 2)
    call add_node(head, 3)
    write (*,*) is_palindrome(head)

contains

subroutine add_node(head, val)
    type(node), pointer, intent(inout) :: head
    integer, intent(in) :: val
    type(node), pointer :: new_node

    allocate(new_node)
    new_node%val = val
    new_node%next => head
    head => new_node

end subroutine add_node

end program test
🌐 Data from online sources 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    if not head or not head.next:
        return True

    fast, slow, prev = head, head, None
    while fast and fast.next:
        fast = fast.next.next
        temp = slow.next
        slow.next = prev
        prev = slow
        slow = temp

    if fast:
        slow = slow.next

    while prev and prev.val == slow.val:
        prev = prev.next
        slow = slow.next

    return prev == None

The function uses the slow and fast pointers approach to find the middle of the linked list. It simultaneously reverses the first half of the linked list. At the end of this process, slow will be at the middle and prev will be the reversed first half of the list. If the list has an odd length, slow moves one step forward (skipping the middle element). Finally, we compare the elements of the reversed first half (using prev) and the rest of the list (starting from slow). If they match, it means the list is a palindrome.

🌐 Data from online sources 
class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

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

    ListNode *fast = head, *slow = head, *prev = NULL;
    while (fast && fast->next) {
        fast = fast->next->next;
        ListNode *temp = slow->next;
        slow->next = prev;
        prev = slow;
        slow = temp;
    }

    if (fast) slow = slow->next;

    while (prev && prev->val == slow->val) {
        prev = prev->next;
        slow = slow->next;
    }

    return prev == NULL;
}

The function uses the slow and fast pointers approach to find the middle of the linked list. It simultaneously reverses the first half of the linked list. At the end of this process, slow will be at the middle and prev will be the reversed first half of the list. If the list has an odd length, slow moves one step forward (skipping the middle element). Finally, we compare the elements of the reversed first half (using prev) and the rest of the list (starting from slow). If they match, it means the list is a palindrome.